XXXIX OM - III - Zadanie 5

Zawody matematyczne:

XXXIX OM, 1987-1988

Etap:

III

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

$ (1) \qquad a_n = a_{n+3}-a_{n+1}a_{n+2} \quad \textrm{dla} \ n = 0, 1, 2, 3, \ldots. $

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

$ (2) \qquad x_m = x_{m+s}, \quad x_{m+1} = x_{m+s+1}, \quad x_{m+2} = x_{m+s+2}. $

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

$ (3) \qquad a_{m-1} = a_{m + 2} - a_ma_{m+1}, $

$ (4) \qquad a_{m + s-1} = a_{m+s+2} - a_{m +s}a_{m + s + 1}. $

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

$ x_{m - 1} =x_{m + s -1}. $

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