XLIX OM - III - Zadanie 4

Dowieść, że w ciągu $ (a_n) $ określonym wzorami

\[<br />
a_1 = 1, \quad a_n = a_{n-1} + a_{[n/2]}\ \textrm{dla}\ n = 2,3,4,\ldots<br />
\]

występuje nieskończenie wiele liczb podzielnych przez $ 7 $.

Uwaga: $ [n/2] $ jest największą liczbą całkowitą nie przekraczającą $ n/2 $.

Rozwiązanie

W ciągu $ (a_n) $ są wyrazy podzielne przez $ 7 $ (na przykład $ a_5 = 7 $). Przypuśćmy, że jest ich skończenie wiele; niech $ a_k $ będzie ostatnim z tych wyrazów. Oznaczmy: $ a_k = x $, $ a_{2k-1} = y $, $ a_{4k-3} = z $; liczba $ x $ dzieli się przez $ 7 $, a liczby $ y $ i $ z $ - nie.

Zachodzą równości:

\[<br />
\begin{array}{llllll}<br />
a_{2k}&=a_{2k-1}+a_{k}&=x+y,&a_{2k+1}&=a_{2k}+a_{k}&=2x+y,\\<br />
a_{4k-2}&=a_{4k-3}+a_{2k-1}&=y+z,&a_{4k-1}&=a_{4k-2}+a_{2k-1}&=2y+z,\\<br />
a_{4k}&=a_{4k-1}+a_{2k}&=x+3y+z,&a_{4k+1}&=a_{4k}+a_{2k}&=2x+4y+z,\\<br />
a_{4k+2}&=a_{4k+1}+a_{2k+1}&=4x+5y+z,&a_{4k+3}&=a_{4k+2}+a_{2k+1}&=6x+6y+z,\\<br />
\end{array}<br />
\]

Przy dzieleniu przez $ 7 $ liczby $ a_{4k-3},a_{4k-2},\ldots,a_{4k+3} $ dają więc takie same reszty jak liczby $ z, z + y, \ldots , z + 6y $. Ponieważ $ y $ nie dzieli się przez $ 7 $, wszystkie te reszty są różne. Zatem jedna z tych siedmiu liczb jest podzielna przez $ 7 $, wbrew przypuszczeniu, że $ a_k $ jest ostatnim takim wyrazem. Sprzeczność kończy dowód.

Komentarze

Dodaj nową odpowiedź