Докажите следующие свойства последовательности Фибоначчи $f_1=1$, $f_2=2$, $\ldots$, $f_{k+1}=f_k+f_{k-1}$:
Каждое натуральное число $n\ge 3$ представляется в виде суммы различных чисел Фибоначчи.
Обозначим количество таких представлений числа $n$ в виде суммы чётного числа слагаемых через $K_n$, в виде суммы нечётного числа слагаемых — через $H_n$; тогда $|K_n-H_n|\le1$ при всех $n$.
Если перемножить несколько подряд стоящих двучленов из последовательности
$$
1-x,\ 1-x^2,\ 1-x^3,\ \ldots,\ 1-x^{~f_k},\ \ldots
$$
(в показателях стоят числа Фибоначчи), то в полученном многочлене все коэффициенты будут равны 0, $-1$ или $+1$.
Известное нам доказательство утверждений б) и в) опирается на такое свойство:
Для любого $n\ge3$ существует единственное представление $n$ в виде суммы различных чисел Фибоначчи, которое вместе с каждым слагаемым $f_k$ ($k\ge3$) содержит хотя бы одно из двух предыдущих чисел Фибоначчи $f_{k-1}$ или $f_{k-2}$.
Для краткости мы будем вместо «представление числа $n$ в виде суммы различных чисел Фибоначчи» говорить «представление числа $n$»; представления, удовлетворяющие условию задачи г), мы будем называть правильными.
Утверждение задачи а) содержится в утверждении задачи г).
Решение задачи г). На полях приведена таблица правильных представлений натуральных чисел. Эта таблица устроена так. Её строки разбиты на группы, содержащие, соответственно, 1, 2, $\ldots$, $f_k$, $\ldots$ равенств. Первая группа состоит из равенства $1=1$, вторая — из равенств $2=2$ и $3=1+2$, а группа с номером $k\ge3$ получается из $(k-2)$-й и $(k-1)$-й групп увеличением левой части входящих в них равенств на $f_k$ и приписыванием к правой части слагаемого $f_k$. Из таблицы видно, что всякое натуральное число $n\ge3$ обладает правильным представлением. Для доказательства единственности правильного представления предположим, что $n$ — самое маленькое число, для которого оно не единственно; пусть
$$
n=f_{i_1}+\ldots+f_{i_m}\quad(i_1\lt\ldots\lt i_m)\tag1
$$
— представление, не содержащееся в нашей таблице. Но тогда правильное представление
$$
n-f_{i_m}=f_{i_1}+\ldots+f_{i_{m-1}}
$$
тоже не может содержаться в таблице, иначе нам пришлось бы при образовании $i_m$-й группы включить в таблицу представление (1). Противоречие.
Решение задачи б). Представления натуральных чисел мы будем изображать в виде последовательностей чёрных и белых кружков: чёрный кружок на $k$-м месте означает, что $f_k$ входит в представление, белый — что не входит (мы обрываем последовательность на последнем чёрном кружке). На рисунке 1 этим способом записаны шесть различных представлений числа 37 (это — все возможные его представления). Правильные представления приобретают при этом вид, показанный на рисунках 2, a или 2, б; здесь $j_1$, $\ldots$, $j_q$ — натуральные числа. В первом случае мы полагаем $n=S(j_1,\ldots,j_q)$, $K_n-H_n=M(j_1,\ldots,j_q)$; во втором случае мы полагаем $n=T(j_1,\ldots,j_q)$, $K_n-H_n=N(j_1,\ldots,j_q)$. (Так, $37=S(2,2,1)$, $M(2,2,1)=K_{37}-H_{37}=3-3=0$; другие примеры приведены рядом на полях.)
Если $n=f_{i_1}+\ldots+f_{i_m}$ — представление числа $n$, включающее в себя $f_r$ и $f_{r+1}$, но не включающее $f_{r+2}$, то, заменив слагаемые $f_r$ и $f_{r+1}$ слагаемым $f_{r+2}$, мы получим другое представление числа $n$. Это преобразование $(\ldots{\bullet}{\bullet}{\circ}\ldots\to\ldots{\circ}{\circ}{\bullet}\ldots)$ мы будем называть элементарным упрощением. Очевидно, всякое представление числа получается из правильного цепочкой элементарных упрощений.
Пусть сначала $q=1$. На рисунке 3 изображён полный набор представлений числа $n=S(j)$ (кстати, равного $f_{j+2}-2$). Мы видим, что $K_{S(j)}$ есть число чётных чисел на отрезке от $\left[\dfrac{j+1}2\right]$ до $j$, а $H_{S(j)}$ есть число нечётных чисел на этом отрезке. Следовательно,
$$
K_n-H_n=M(j)=\begin{cases}
\hphantom{-1}\mathllap1,&\text{если}~j\equiv0\bmod4,\\
-1,&\text{если}~j\equiv1\bmod4,\\
\hphantom{-1}\mathllap0,&\text{если}~j\equiv2\bmod4.
\end{cases}
$$
Обратимся теперь к числу $M(j_1,\ldots,j_q)$. Разделим представления числа $S(j_1,\ldots,j_q)$ на две группы: представления вида $f_1+\ldots+f_{j_1}+\ldots$ и остальные. Число представлений первой группы совпадает с числом всех представлений числа $S(j_2,\ldots,j_q)$, только последние имеют на $j_1$ слагаемых меньше, поэтому вклад первой группы в $M(j_1,\ldots,j_q)$ равен $(-1)^{j_1}M(j_2,\ldots,j_q)$ (на полях приведено несколько числовых примеров, иллюстрирующих наше наблюдение).
Далее. Чтобы с помощью элементарных упрощений получить из правильного представления представление второй группы, необходимо сделать элементарное упрощение $(f_{j_1-1},f_{j_1})\to f_{j_1+1}$, причём с него можно начать. В результате между первыми $j_1-2$ слагаемыми и остальными возникнет зазор длины 2 (рис. 4), исключающий возможность взаимодействия. Поэтому в дальнейшем элементарные упрощения первых $j_1-2$ слагаемых и остальных происходят независимо, так что вклад второй группы в $M(j_1,\ldots,j_q)$ равен $M(j_1-2)\,M(j_2+1,j_3,\ldots,j_q)$. Итак,
$$
M(j_1,\ldots,j_q)=(-1)^{j_1}M(j_2,\ldots,j_q)+M(j_1-2)\,M(j_2+1, j_3,\ldots,j_q)\tag3
$$
(см. также примеры на полях). Докажем теперь индукцией по $q$, что $M(j_1,\ldots,j_q)=-1$, 0 или 1.
При $q=1$ это мы уже знаем. Предположим, что $M(k_1,\ldots,k_r)=-1$, 0 или 1 при $r=q$ и любых $k_1$, $\ldots$, $k_r$. Если $j_1\equiv0$ или $1\bmod4$, то $M(j_1-2)=0$ (см. формулу (2)) и $$
M(j_1,\ldots,j_q)=(-1)^{j_1}M(j_2,\ldots,j_q)=-1{,}~0~\text{или}~1.
$$
Если $j_1\equiv 2$ или $3\bmod4$, то $M(j_1-2)=(-1)^{j_1}$ (см. формулу (2)) при $q=2$ и $$
\begin{gather*}
M(j_1,\ldots,j_q)=(-1)^{j_1}[M(j_2,\ldots,j_q)+M(j_2+1,j_3,\ldots,j_q)]=\\
=(-1)^{j_1}[(-1)^{j_2}M(j_3,\ldots,j_q)+(-1)^{j_2+1}M(j_3,\ldots,j_q)+{}\\
{}+M(j_2-2)\,M(j_3+1,j_4,\ldots,j_q)+M(j_2-1)\,M(j_3+1,j_4,\ldots,j_q)]=\\
=(-1)^{j_1}(M(j_2-2)+M(j_2-1))\,M(j_3+1,j_4,\ldots,j_q)
\end{gather*}
$$
при $q\ge3$. В обоих случаях мы получаем, что $M(j_1,\ldots,j_q)=0$, 1 или $-1$, поскольку, как видно из формулы (2), $M(j_2)+M(j_2+1)=0$, 1 или $-1$ и $M(j_2-2)+M(j_2-1)=0$, 1 или $-1$.
Точно так же можно показать, что $N(j_1,\ldots,j_q)=0$, 1 или $-1$. Более того, ясно, что отсутствие в правильном представлении слагаемого $f_1$ никакого воздействия на ход элементарных упрощений не окажет, так что в действительности $N(j_1,\ldots,j_q)=M(j_1,\ldots,j_q)$.
Решение задачи в). Эта задача близка к задаче б), и мы ограничимся несколькими замечаниями, которые позволят читателю без труда восстановить её решение.
Коэффициент при $x^n$ в произведении $(1-x^{f_l})(1-x^{f_{l+1}})\ldots(1-x^{f_m})$ равен разности $K-H$, где $K$ — число представлений числа $n$ в виде суммы чётного числа различных слагаемых из множества $\{f_l,f_{l+1},\ldots,f_m\}$, а $H$ — число представлений числа $n$ в виде суммы нечётного числа таких слагаемых (см. поля). Другими словами, $K$ и $H$ отличаются от прежних $K_n$ и $H_n$ тем, что запрещается брать числа Фибоначчи с номерами, меньшими, чем $l$, и большими, чем $m$, а наша задача по-прежнему заключается в том, чтобы показать, что $K-H=-1$, 0 или 1. Прежде всего нужно изменить определение правильного представления: оно должно включать в себя только слагаемые из нашего множества (разумеется, неравенство $k\ge3$ в определении должно быть заменено неравенством $k\ge l+2$). Утверждение задачи г) ослабляется: теперь всякое число либо вовсе не имеет правильных представлений, либо имеет одно такое представление. По-прежнему всякое представление получается из правильного цепочкой элементарных упрощений (так что число, не имеющее правильных представлений, не имеет никаких представлений). Числа $S(j_1,\ldots,j_q)$ и $T(j_1,\ldots,j_q)$ определяются как в решении задачи б), только правильное представление числа $S(j_1,\ldots,j_q)$ начинается теперь со слагаемого $f_l$, а правильное представление числа $T(j_1,\ldots,j_q)$ — со слагаемого $f_{l+1}$. Определения чисел $M(j_1,\ldots,j_q)$ и $N(j_1,\ldots,j_q)$ и формула (3) не меняются. Некоторой аккуратности требует вычисление в новой обстановке чисел $M(j)$ (и $N(j)$), но читатель с этим вычислением наверняка справится.
Замечание. Читатели, познакомившиеся с помещённой в этом номере журнала статьёй «О раскрытии скобок, об Эйлере, Гауссе, Макдональде и об упущенных возможностях», вероятно, обратили внимание на сходство, во всяком случае внешнее, между утверждением только что разобранной задачи и тождеством Эйлера. Это сходство явилось одной из главных причин интереса к задаче со стороны её авторов.
От редакции. Другое решение задачи М659 мы получили от нашего читателя Ляонаса Меркявичюса. В его работе используются такие обозначения: через $K(n,k)$, соответственно $H(n,k)$, обозначается число представлений числа $n$ в виде суммы чётного, соответственно нечётного, числа различных слагаемых, выбираемых из множества $\{f_1,\ldots,f_k\}$; через $G(n,k)$ — разность $K(n,k)-H(n,k)$. После этого доказываются четыре формулы:
$$
\colsep{0pt}{\begin{array}{ll}
G(n,k)=0&\text{при}~n\gt f_{k+2}-2;\\
G(n,k)=(-1)^kG(f_{k+2}-2-n,k)\quad&\text{при}~0\le n\le f_{k+2}-2;\\
G(n,k)=G(n,k-1)&\text{при}~0\le n\lt f_k;\\
G(n,k)=-G(n-f_{k-1},k-3)&\text{при}~f_k\le n\lt f_k+f_{k-2}.
\end{array}}
$$
(Первые три из этих формул почти очевидны, так что вся трудность заключена в доказательстве последней.) С помощью этих формул индукцией по $k$ легко показать, что $G(n,k)=0$ или $\pm1$ (нужно только проверить это для $k=1$, 2, 3). После этого для решения задачи б) достаточно заметить, что $M(n)=G(n,k)$ при $f_{k+1}\gt n$, а для решения задачи в) — что коэффициент при $x^n$ в произведении $(1-x^{f_{i+1}})\ldots(1-x^{f_{i+k}})$ равен 0, если $n$ не представляется в виде суммы различных слагаемых, выбираемых из множества $\{f_{i+1},\ldots,f_{i+k}\}$, и равен $G(f_{j_1}+f_{j_2}+\ldots+f_{j_s},k)$, если $n=f_{i+j_1}+\ldots+f_{i+j_s}$, $1\le j_1\lt \ldots\lt j_s\le k$.
