Задача М1120‍‍

Докажем общее утверждение: если последовательность $a_0=0$‍,‍ $a_1$‍,‍ $a_2$‍,‍ $a_3$‍,‍ $\ldots$‍‍ целых чисел такова, что $$\gcd(a_m,a_k)=\gcd(a_{m-k},a_k)\tag1$$ для любых $m\gt k\ge 1$‍,‍ то $$\gcd(a_m,a_k)=a_d,\tag2$$ где $d=\gcd(m,k)$‍.‍

В самом деле, для любой пары начальных значений $m$‍,‍ $k$‍‍ повторение операции $$(m,k)\to(m-k,m)$$ (из большего числа пары вычитается меньшее) приводит к паре $(d,0)$‍,‍ где $d=\gcd(m,k)$‍;‍ это вариант алгоритма Евклида для отыскания наибольшего общего делителя чисел $m$‍,‍ $n$‍,‍ изложенный в учебнике информатики для 9 класса (обычно алгоритмом Евклида называют его «сокращённый» вид, состоящий из последовательности делений с остатком).

Таким образом, из равенств (1) следует, что $$\gcd(a_m,a_k)=\gcd(a_d,a_0)=\gcd(a_d,0)=a_d$$ ‍— это и есть (2).

а) Положим $\underbrace{P(P(P\ldots(P}_n(x))\ldots))=P_n(x)$‍;‍ это многочлен с целыми коэффициентами, причём $a_m=P_m(a_0)$‍‍ и $a_m=P_{m-k}(a_k)$‍‍ при $m\gt k$‍.‍ Заметим, что $P_n(x)=a_n+xQ_n(x)$‍,‍ где $Q_n(x)$‍‍ — тоже многочлен с целыми коэффициентами. Проверим (1): при $m\gt k\ge1$‍‍ $$\gcd(a_m,a_k)=\gcd(P_{m-k}(a_k),a_k)=\gcd(a_{m-k}+a_kQ_{m-k}(a_k),a_k)=\gcd(a_{m-k},a_k).$$

б) Для чисел Фибоначчи при любых $m\gt k\ge0$‍‍ выполнено равенство $$a_m=a_{m-k}a_{k+1}+a_{m-k-1}a_k.\tag3$$ В самом деле, $a_m=a_{m-1}+a_{m-2}$‍‍ (при $k=1$‍),‍ $$ \begin{alignat*}{2} a_m&=2a_{m-2}+a_{m-3}&&\quad (k=2),\\ a_m&=3a_{m-3}+2a_{m-4}&&\quad (k=3) \end{alignat*} $$ и вообще, если уже доказано (3), то $$ \begin{gather*} a_m=(a_{m-k-1}+a_{m-k-2})a_{k+1}+a_{m-k-1}a_k=\\ =a_{m-k-1}(a_{k+1}+a_k)+a_{m-k-2}a_{k+1}=\\ =a_{m-k-1}a_{k+2}+a_{m-k-2}a_{k+1} \end{gather*} $$ ‍— это то же равенство (3), где вместо $k$‍‍ стоит $k+1$‍.‍ Таким образом, (3) доказывается индукцией по $k$‍.‍

Отметим, что утверждение задачи б) известно как «теорема Лукача» (1876 г.).