XL OM - II - Zadanie 5

Dany jest ciąg $ (c_n) $ liczb naturalnych określony rekurencyjnie: $ c_1 = 2 $, $ c_{n+1} = \left[ \frac{3}{2}c_n\right] $. Udowodnić, że wśród wyrazów tego ciągu jest nieskończenie wiele liczb parzystych i nieskończenie wiele liczb nieparzystych.

Rozwiązanie

Wystarczy udowodnić następujące dwa stwierdzenia:

(a) Dla dowolnej liczby parzystej $ p $ będącej wyrazem ciągu $ (c_n) $ istnieje większa od niej liczba nieparzysta będąca wyrazem tego ciągu.

(b) Dla dowolnej liczby nieparzystej $ q $ będącej wyrazem ciągu $ (c_n) $ istnieje większa od niej liczba parzysta będąca wyrazem tego ciągu.

Dowód zdania (a). Niech $ p = 2^km $, $ k,m \geq1 $, $ m $ nieparzyste. Jeśli $ p = c_n $ , to $ c_{n+1} = 2^{k-1}\cdot  3m $ ; gdy $ k -1 \geq 1 $, wówczas $ c_{n+2} = 2^{k-2}\cdot 3^2m $; itd., ogólnie, dla $ j \in \{1,\ldots, k\} $ mamy $ c_{n-j} = 2^{k-j} \cdot 3^j m $. W szczególności dla $ j = k $ dostajemy $ c_{n+k} = 3^km $. Jest to większa niż p liczba nieparzysta.

Dowód zdania (b). Teraz $ q - 1 $ jest liczbą parzystą, dodatnią ($ q - 1 $ nie może być zerem, bo $ c_n \geq 2 $ dla wszystkich $ n $; to wynika przez natychmiastową indukcję z określenia ciągu $ (c_n) $). Zatem $ q = 2^km+1 $, $ k,m \geq 1 $, $ m $ nieparzyste. Jeśli $ q = c_n $ , to $ c_{n+1} = 2^{k-1}\cdot 3m + 1 $ i ogólnie, jak poprzednio, dla $ j\in \{1, \ldots, k\} $ mamy $ c_{n+j} = 2^{k-j}\cdot 3^jm+1 $; w szczególności $ c_{n+k} = 3^km + 1 $. Jest to większa niż $ q $ liczba parzysta.

Komentarze

Dodaj nową odpowiedź