XXXIX OM - I - Zadanie 11

Zawody matematyczne:

XXXIX OM, 1987-1988

Etap:

Dany jest ciąg określony wzorami $a_0 = 0$ , $a_1 = 1$ , $a_2 = 2$ , $a_3 = 6$ , $a_{n+4} = 2a_{n+3} + a_{n+2} - 2 a_{n+1} - a_n$ dla $n > 0$ . Udowodnić, że $a_n$ jest liczbą podzielną przez $n$ .

Rozwiązanie

Niech $(v_n)$ będzie ciągiem Fibonacciego, czyli ciągiem liczb całkowitych określonym przez warunki: $v_0 = 0$ , $v_1 = 1$ , $v_{n+2} = v_n+v_{n+1}$ (por. zadanie przygotowawcze $F$ ; tym razem wygodnie jest numerować wyrazy ciągu od zera, przyjmując $v_0 = 0$ ). Wykażemy, że $a_n = nv_n$ dla $n=0, 1, 2, \ldots$ .

Dla $n = 0, 1, 2, 3$ jest to prawda. Ustalmy $n \geq 4$ i załóżmy, że $a_k = kv_k$ dla $k <n$ . Pisząc dla wygody: $v_{n-1} = x$ , $v_{n-2} = y$ mamy $v_n = x+y$ , $v_{n-3} = x-y$ , $v_{n-4} = 2y-x$ , skąd

$ \begin{split} a_n-nv_n & = 2a_{n-1}+a_{n-2}-2a_{n-3} - a_{n-4} -nv_n =\\ & = 2(n- 1)x+ (n-2)y-2(n-3) (x-y) - \\ - (n-4)(2y-x)-n(x+y) = 0. \end{split} $

Na mocy zasady indukcji równość $a_n = nv_n$ zachodzi dla wszystkich całkowitych $n \geq 0$ . Zatem każda z liczb $a_n$ jest całkowitą wielokrotnością $n$ .