Математикадан республикалық олимпиада, 1998-1999 оқу жылы, 11 сынып

${{a}_{1}},{{a}_{2}},\ldots {{a}_{1999}}$ натурал сандар тізбегінде ${{a}_{n}}-{{a}_{n-1}}-{{a}_{n-2}}$ саны 100-ге бөлінеді $\left( 3\le n\le 1999 \right)$. ${{a}_{1}}=19$ және ${{a}_{2}}=99$ болса, онда $a_{1}^{2}+a_{2}^{2}+\ldots +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?