Республиканская олимпиада по математике, 1999 год, 11 класс

В последовательности натуральных чисел $a_1$, $a_2$, $\dots$, $a_{1999}$, $a_n-a_{n-1}-a_{n-2}$ делится на 100 $(3\leq n \leq 1999)$. Известно, что $a_1=19$ и $a_2=99$. Найдите остаток от деления числа $a_1^2+a_2^2+ \dots +a_{1999}^2$ на 8.

Комментарий/решение

$$\forall n\in [3,1999] : \quad a_n-a_{n-1}-a_{n-2}\equiv 0 \quad (mod 100) \Leftrightarrow a_n=100k_n+a_{n-1}+a_{n-2}$$

$$\Leftrightarrow a_n=100k_n+99F_{n-1}+19F_{n-2}$$

$$a_1^2+a_2^2+...+a_{1999}^2=19^2+99^2+\sum_{n=3}^{1999} (100k_n+99F_{n-1}+19F_{n-2})^2=$$

$$=(20-1)^2+(100-1)^2+\sum_{n=3}^{1999} (100k_n+(100-1)F_{n-1}+(20-1)F_{n-2})^2\equiv$$

$$\equiv 1^2+1^2+\sum_{n=3}^{1999} (F_{n-1}+F_{n-2})^2 \quad (mod 8)$$

$$1^o. \quad F_1^2+F_2^2+...+F_n^2=F_nF_{n+1} \qquad 2^o. \quad F_n \vdots F_m \Leftrightarrow n \vdots m$$

$$1^2+1^2+\sum_{n=3}^{1999} (F_{n-1}+F_{n-2})^2= \sum_{n=1}^{1999} F_{n}^2=F_{1999}F_{2000}$$

$$A=F_{1999}F_{2000}= F_{1999}(F_{1999}+F_{1998}) \equiv F_{1999}^2 \quad (mod 8)\Leftrightarrow F_{1998} \vdots F_6=8$$

$$F_{1999}^2 \equiv F_{1}^2=1 \quad (mod 8)$$

$$Ответ: 1 \quad \qquad (a_1^2+a_2^2+...+a_{1999}^2=8k+1)$$

А что такое F_n?