XLIX OM - III - Zadanie 2

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

\[<br /> F_0 = F_1 = 1,\ F_{n+2} = F_n + F_{n+1} \ \textrm{dla}\ n = 0,1, 2,\ldots .<br /> \]

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

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

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

\[<br /> (1)\qquad x_0=\frac{F_{2r}}{F_{2r+1}}=\frac{F_k}{F_m}.<br /> \]

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

\[<br /> \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,<br /> \]

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

\[<br /> (2)\qquad x_n=\frac{F_{k-2n}}{F_{k+1-2n}}\ \textrm{dla}\ n\leq\frac{k}{2}.<br /> \]

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 $.

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Komentarze

Dodaj nową odpowiedź