XXXIX OM - III - Zadanie 5

Ciąg $ (a_n) $ określony Jest warunkami $ a_1 = a_2 = a_3 = 1 $, $ a_{n+1} = a_{n+2}a__{n+1}+a_n $ ($ n \geq 1 $). Wykazać, że dla każdej liczby naturalnej $ r $ istnieje taka liczba $ s $, że $ a_s $ jest podzielne przez $ r $.

Rozwiązanie

Gdy $ r=1 $, nie ma czego dowodzić. W dalszym ciągu zakładamy, że $ r \geq 2 $.

Przyjmijmy $ a_0 = 0 $ i rozważajmy ciąg $ (a_n) $ indeksowany nieujemnymi liczbami całkowitymi. Dana w zadaniu zależność rekurencyjna jest zachowana; możemy ją przepisać w równoważnej postaci

\[<br /> (1) \qquad a_n = a_{n+3}-a_{n+1}a_{n+2} \quad \textrm{dla} \ n = 0, 1, 2, 3, \ldots.<br /> \]

Zajmiemy się ciągiem $ (x_0, x_1 x_2, x_3, \ldots) $, gdzie $ x_n $ jest resztą z dzielenia $ a_n $ przez $ r $. Niech $ Z_r^3 $ będzie zbiorem wszystkich uporządkowanych trójek liczb ze zbioru $ \{0, 1, \ldots, r-1\} $. Dla każdego $ n \geq 0 $ trójka $ T_n = (x_n, x_{n+1}, x_{n+2}) $ należy do $ Z_r^3 $. Ponieważ $ Z_r^3 $ jest zbiorem skończonym, w ciągu $ (T_0, T_1, T_2, T_3, \ldots) $ muszą wystąpić powtórzenia. Innymi słowy, istnieją liczby całkowite $ m \geq 0 $, $ s > 0 $ takie, że $ T_m = T_{m+s} $, czyli

\[<br /> (2) \qquad x_m = x_{m+s}, \quad x_{m+1} = x_{m+s+1}, \quad x_{m+2} = x_{m+s+2}.<br /> \]

Niech $ m \geq 0 $ będzie najmniejszym numerem, dla którego istnieje $ s > 0 $ spełniające związki (2) (czyli równość $ T_m= T_{m+s} $). Wykażemy, że $ m = 0 $. Przypuśćmy, że jest inaczej, tzn. $ m \geq 1 $. Podstawmy w (1) $ n = m-1 $ oraz $ n = m+s- 1 $. Otrzymamy równości

\[<br /> (3) \qquad a_{m-1} = a_{m + 2} - a_ma_{m+1},<br /> \]
\[<br /> (4) \qquad a_{m + s-1} = a_{m+s+2} - a_{m +s}a_{m + s + 1}.<br /> \]

Ze związków (2) wynika, że prawe strony równości (3) i (4) dają przy dzieleniu przez $ r $ jednakowe reszty; wobec tego i lewe strony muszą dawać jednakowe reszty. A zatem

\[<br /> x_{m - 1} =x_{m + s -1}.<br /> \]

To zaś, w połączeniu z dwiema pierwszymi równościami (2), oznacza, że trójki $ T_{m-1} = (x_{m-1}, x_m, x_{m+1}) $ i $ T_{m-1+s} = (x_{m+1+s}, x_{m+s}, x_{m+1+s}) $ są identyczne - wbrew minimalności wskaźnika $ m $. Otrzymana sprzeczność pokazuje niesłuszność przypuszczenia, że $ m \geq 1 $. Zatem $ m = 0 $.

Pierwsza z równości (2) przybiera teraz postać $ x_0 = x_s $. Ale $ x_0 = 0 $ (bo $ a_0 = 0 $). Wobec tego i $ x_s = 0 $. A to znaczy, że $ a_s $ dzieli się przez $ r $.

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

Komentarze

Dodaj nową odpowiedź