92高中數學能力競賽

想請教各位老師們如何證明

[問題四]：令Q+表正有理數集，N表自然數集，定義f：NQ+如下：
f(1)=1f(2n)=f(n)+1f(2n+1)=1f(2n)。
(a)求證若f(x)=f(y)則x=y。
(b)求證對任意qQ+必存在一個自然數n，使得f(n)=q。

(a) 首先我們看到 xy 的奇偶性必相同，理由如下：
若 z 為正偶數，則 f(z)=f(z2)+11
當 z=1 時，f(z)=1
若 z 為大於 1 的正奇數，則 f(z)=1f(z−1)1

將命題" 若 f(x)=f(y) 且 xym，則 x=y" 對 mN 作數學歸納法
(1) 當 m=1 時，
     設 f(x)=f(y) 且 xy1，則 x=1y=1，故 x=y，命題成立
(2) 設 m=M 時，命題成立
(3) 則當 m=M+1 時，設 f(x)=f(y) 且 xyM+1，
      則 xy 同奇偶
      若 xy 均為偶數 則 f(\frac x2) = f(x) -1 = f(y) - 1 = f(\frac y2)
                                   而 \frac x2, \frac y2 \leq M ，由歸納法假設得 \frac x2 = \frac y2 ，因此 x=y
      若 x,y 均為奇數 則 f(x-1) = \frac 1{f(x)} = \frac 1{f(y)} = f(y-1)
                                   而 x-1, y-1 \leq M ，由歸納法假設得 x-1 = y-1 ，因此 x=y
故由數學歸納法得 m 為任意正整數時，命題均成立，即 " 若 f(x)=f(y) ，則 x=y "

(b) 也是數學歸納法，把 q 寫作 q = \frac ba
設 a + b \leq m ，對 m 作數學歸納法
過程基本上同 (a)，也是利用遞迴關係式去找另一個分子分母和比較小的情況，找到後，再乘2或 乘 2加1，就可以了

舉例來說， q= \frac 25 ，利用歸納法假設去找 x 滿足 f(x) = \frac{5-2}{2} ，則 f(2x+1) = \frac 1{f(2x)} = \frac 25

謝謝，再來研究一下