XLIX OM - III - Zadanie 2

Zawody matematyczne:

XLIX OM, 1997-1998

Etap:

III

Ciąg Fibonacciego $(F_n)$ jest dany wzorami:

$ F_0 = F_1 = 1,\ F_{n+2} = F_n + F_{n+1} \ \textrm{dla}\ n = 0,1, 2,\ldots . $

Wyznaczyć wszystkie pary $(k, m)$ liczb całkowitych $m > k \geq 0$ , dla których w ciągu $(x_n)$ określonym wzorami

$ x_0=\frac{F_k}{F_m}, \quad x_{n+1}= \left\{\begin{array}{cll} \frac{2x_n-1}{1-x_n}&\textrm{gdy}&x_n \neq 1\\ 1&\textrm{gdy}&x_n = 1 \end{array}\right. \quad (n=0,1,2,3,\ldots) $

występuje liczba $1$ .

Rozwiązanie

Załóżmy, że dla pewnej liczby całkowitej $r \geq 0$ zachodzi równość: $x_r = 1$ , przy czym $r$ jest najmniejszym numerem o tej własności. Jeśli $r = 0$ , to $F_k = F_m$ , skąd $k = 0$ , $m = 1$ . Dalej zakładamy, że $r \geq 1$ . W podanym wzorze rekurencyjnym podstawiamy $n = r - 1$ i wyznaczamy $x_{r-1} = 2/3$ . Zgadujemy, że $x_{r-j} = F_{2j}/F_{2j+1}$ dla $j = 0,1,\ldots, r$ i dowodzimy słuszności tego przypuszczenia przez łatwą indukcję. Dla $j = r$ otrzymujemy

$ (1)\qquad x_0=\frac{F_{2r}}{F_{2r+1}}=\frac{F_k}{F_m}. $

Wykażemy teraz, że $m = k + 1$ oraz że $k$ jest liczbą parzystą. (Nietrudno wykazać, że nawet $k = 2r$ .) Gdyby zachodziła nierówność $m \geq k + 2$ , mielibyśmy

$ \frac{F_m}{F_k}-1\geq \frac{F_{k+2}}{F_k}-1=\frac{F_{k+1}}{F_k}\geq 1 >\frac{F_{2r-1}}{F_{2r}}=\frac{F_{2r+1}}{F_{2r}}-1, $

wbrew równości (1). Zatem $m = k + 1$ , czyli $x_0 = F_k/F_{k+1}$ . Gdy wyraz początkowy $x_0$ ma tę postać, z rekurencyjnej definicji ciągu $(x_n)$ , otrzymujemy przez łatwą indukcję wzór

$ (2)\qquad x_n=\frac{F_{k-2n}}{F_{k+1-2n}}\ \textrm{dla}\ n\leq\frac{k}{2}. $

Przypuśćmy, że $k$ jest liczbą nieparzystą i przyjmijmy $\ell = (k-1)/2$ . Wówczas, na mocy wzoru (2), $x_n < 1$ dla $n < \ell$ oraz $x_\ell= F_1/F_2 = 1/2$ , skąd $x_{\ell+1} = 0$ , $x_{\ell+2} = -1$ i wszystkie dalsze wyrazy są ujemne. W ciągu $(x_n)$ nie występuje więc liczba $1$ , wbrew temu, że $x_r = 1$ . Liczba $k$ musi więc być parzysta.

Wykazaliśmy zatem, że jeśli w rozważanym ciągu występuje liczba $1$ , to para $(k,m)$ jest postaci $(2r, 2r + 1)$ dla pewnej liczby całkowitej $r \geq 0$ .

Na odwrót: jeśli $k = 2r$ , $m = 2r + 1$ , gdzie $r$ jest dowolną liczbą całkowitą nieujemną, to $x_0 = F_k/F_{k+1}$ , skąd na mocy wzoru (2) widzimy, że ciąg $(x_n)$ zawiera wyraz $x_r = F_0/F_1 = 1$ .