Азиатско-Тихоокеанская математическая олимпиада, 2006 год

Докажите, что любое натуральное число можно представить в виде конечной суммы различных целых степеней золотого сечения $\tau =\frac{1+\sqrt{5}}{2}$. Здесь под целой степенью золотого сечения $\tau $ понимается число вида ${{\tau }^{i}}$, где $i$ — целое (не обязательно положительное).

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

Заметим, что верно следующее тождество $r^2 = r + 1 \Rightarrow r^{j+2} = r^{j+1} + r^j, \, \forall j \in \mathbb{Z}$. Пусть мы хотим представить число $N$. Тогда представим $N$ в $r$-ичной системе счисления. То есть $a_{k}a_{k-1}...a_{0}...a_{-k}$, где $a_{i} \in \{0, 1\}$. Будем доказывать задачу по индукции.

База: $N=1$, очевидна. $1 = r ^ 0$.

Предположение: мы смогли представить $N-1$ в виде суммы степеней золотого сечения.

Переход: Покажем, что можно представить $N$. Рассмотрим $r$-ичное представление числа $N-1$. Если $a_{j} = a_{j+1} = 1$ то можно заменить $a_{j+2}$ на $1$ и $a_{j}, a_{j+1}$ на $0$. Значит мы можем считать, что в $r$-ичной записи нет двух единиц подряд. Если $a_{0} = 0$, то заменяя значение на $1$ мы представляем в требуемом виде число $N$. Значит $a_{0} = 1$. Если $a_{-1} = a_{-2} = 0$, то заменяя $a_{0} = 0, \, a_{-1} = a_{-2} = 1$ представляем в требуемом виде $N$. Значит $a_{-1} = 0, \, a_{-2} = 1$. Делая аналогичное рассуждения мы получим, что $a_{0} = a_{-2} = a_{-4} = ... = 1$. Но так как $r$-ичная запись числа $N-1$ содержит конечное число разрядов, то в какой то момент $r_{-2k} = 0$, после чего последовательно заменяя все $r_{-2i}$ на $0$, получим что $r_{0} = 0$, и значит можно представить число $N$ в виде суммы различных степеней золотого сечения, что и требовалось доказать.