XXXIX OM - I - Zadanie 11

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

\[<br />
\begin{split}<br />
a_n-nv_n & = 2a_{n-1}+a_{n-2}-2a_{n-3} - a_{n-4} -nv_n =\\<br />
& = 2(n- 1)x+ (n-2)y-2(n-3) (x-y) - \\<br />
- (n-4)(2y-x)-n(x+y) = 0.<br />
\end{split}<br />
\]

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