Определим последовательность $b_n$ условиями: $b_1=0$, $b_2=2$, $b_3=3$, $b_{n+1}=b_{n-1}+b_{n-2}$ при $n\ge3$. Докажите, что при простом $p$ число $b_p$ делится на $p$.
Приведём два решения. Первое основано на комбинаторной интерпретации чисел $b_n$.
Возьмём окружность, поделённую точками $A_0$, $A_1$, $\ldots$, $A_{n-1}$ на $n$ равных частей, и рассмотрим её разбиения на дуги, составленные из двух или трёх частей; назовём их «подходящими $n$-разбиениями». Пусть $a_n$ — число таких разбиений. Тогда, очевидно, $a_1=0$, $a_2=2$, $a_3=3$. Докажем, что $a_{n+1}=a_{n-1}+a_{n-2}$ при $n\ge3$, а значит, $a_n=b_n$ при всех $n$. Для этого поставим в соответствие каждому подходящему $(n+1)$-разбиению либо $(n-1)$-разбиение, либо $(n-2)$-разбиение, и покажем, что полученное соответствие взаимно однозначно.
Стянем в точку ту дугу произвольного подходящего $(n+1)$-разбиения, которая следует за дугой, содержащей $A_0$, при обходе по часовой стрелке. (Если точка $A_0$ оказалась между двумя дугами, то стягивается дуга, начинающаяся в этой точке при указанном направлении обхода; см. рисунок.) Чтобы восстановить по $(n-1)\text{-}$ или $(n-2)$-разбиению исходное $(n+1)$-разбиение, достаточно вставить дугу соответственно из двух или трёх частей вслед за дугой, содержащей $A_0$ (а если $A_0$ — граница двух дуг, то между этими дугами). В силу обратимости нашего соответствия оно взаимно однозначно.
Рассмотрим теперь все подходящие $p$-разбиения при простом $p$. Объединим в одну группу те из них, которые получаются друг из друга поворотами на углы $\dfrac{2\pi k}p$, $k=0$, 1, $\ldots$, $p-1$. Заметим, что повороты на $\dfrac{2\pi k_1}p$ и $\dfrac{2\pi k_2}p$ при $k_1\ne k_2$ переводят данное разбиение в разные. (В противном случае мы имели бы разбиение, которое переходит в себя при повороте на $\dfrac{2\pi k}p$, где $k=k_1-k_2$, а значит, и при всех поворотах на $\dfrac{2\pi k}p\cdot n$, $n=0$, 1, $\ldots$, $p-1$. Но при простом $p$ один из этих поворотов совпадает с поворотом на $\dfrac{2\pi}p$, а такой поворот не может переводить в себя никакое подходящее разбиение.) Итак, в каждой группе ровно $p$ разбиений, следовательно, $b_p=a_p$ делится на $p$.
Второе решение — чисто алгебраическое, однако использует некоторые факты, выходящие за пределы школьной программы.
Пусть $\lambda_1$, $\lambda_2$, $\lambda_3$ — три корня уравнения $t^3-t-1=0$ (два из них — комплексные числа). Тогда каждая из последовательностей $\lambda_1^n$, $\lambda_2^n$, $\lambda_3^n$, а значит, и их сумма $a_n=\lambda_1^n+\lambda_2^n+\lambda_3^n$ удовлетворяет соотношению $a_{n+1}=a_{n-1}+a_{n-2}$. При этом по теореме Виета (получающейся раскрытием скобок в равенстве $(t-\lambda_1)(t-\lambda_2)(t-\lambda_3)=t^3-t-1$)
$$
a_1=\lambda_1+\lambda_2+\lambda_3=0,\quad
\lambda_1\lambda_2+\lambda_2\lambda_3+\lambda_3\lambda_1=-1,\quad \lambda_1\lambda_2\lambda_3=1,
$$
откуда
$$
\begin{align*}
a_2&=\lambda_1^2+\lambda_2^2+\lambda_3^2=(\lambda_1+\lambda_2+\lambda_3)^2-
2(\lambda_1\lambda_2+\lambda_2\lambda_3+\lambda_3\lambda_1)=2;\\[5pt]
a_3&=\lambda_1^3+\lambda_2^3+\lambda_3^3=(\lambda_1+\lambda_2+\lambda_3)^3-
3(\lambda_1+\lambda_2+\lambda_3)\times{}\\&\qquad\qquad\qquad\qquad\qquad
{}\times(\lambda_1\lambda_2+\lambda_2\lambda_3+\lambda_3\lambda_1)+
3\lambda_1\lambda_2\lambda_3=3.
\end{align*}
$$
Следовательно, $a_n=b_n$ при всех $n$.
Теперь заметим, что $$
a_p=\lambda_1^p+\lambda_2^p+\lambda_3^p=(\lambda_1+\lambda_2+\lambda_3)^p-
\textstyle\sum C_p^{(k,\,l,\,m)}\lambda_1^k\lambda_2^l\lambda_3^m,
$$
где суммирование ведётся по всем наборам $(k,l,m)$ целых неотрицательных чисел с суммой $k+l+m=p$, отличным от $(p,0,0)$, $(0,p,0)$ и $(0,0,p)$, а $$
C_p^{(k,\,l,\,m)}=\frac{p!}{k!\,l!\,m!},
$$
и докажем, что при простом $p$ число $a_p$ делится на $p$.
Ясно, что для указанных наборов $(k,l,m)$ коэффициент $C_p^{(k,\,l,\,m)}$ делится на простое $p$. Далее, выделим в сумме группы слагаемых, отличающихся только перестановкой показателей $k$, $l$, $m$. Коэффициенты $C_p^{(k,\,l,\,m)}$ у всех таких слагаемых одинаковы, а сумма соответствующих одночленов $\lambda_1^k\lambda_2^l\lambda_3^m$ — это так называемый симметрический многочлен от $\lambda_1$, $\lambda_2$, $\lambda_3$ (т. е. не меняющийся при перестановках аргументов). Известно, что такой многочлен всегда можно представить как некий многочлен с целыми коэффициентами от основных симметрических функций
$\sigma_1=\lambda_1+\lambda_2+\lambda_3$,
$\sigma_2=\lambda_1\lambda_2+\lambda_2\lambda_3+\lambda_3\lambda_1$,
$\sigma_3=\lambda_1\lambda_2\lambda_3$ — это частный случай основной теоремы о симметрических многочленах (см., например, книгу В. Г. Болтянского, Н. Я. Виленкина «Симметрия в алгебре», М.: Наука, 1987). У нас числа $\sigma_1=0$, $\sigma_2=-1$, $\sigma_3=1$ — целые, поэтому сумма слагаемых каждой группы, а значит, и вся сумма делится на $p$. Тем самым, поскольку $\lambda_1+\lambda_2+\lambda_3=0$, и $a_p$ делится на $p$.
