Теоретико-числовые свойства чисел Фибоначчи

Рассмотрим произвольное представление произвольного числа описанное в задаче. Если  – его наибольшее слагаемое, то докажем, что Будем доказывать это утверждение индукцией по База очевидна. Теперь покажем переход. Действительно, равносильно Рассмотрим представление числа полученное из представления вычеркиванием слагаемого Согласно условию задачи, оно не содержит слагаемого поэтому его наибольшее слагаемое не превосходит откуда, по предположению индукции, что и требовалось доказать.

Из доказанного утверждения немедленно следует единственность. Действительно, пусть у какого-то существует два различных представления. Сократим все их общие слагаемые. Так как представления различны, сократятся не все слагаемые, и мы получим два представления некоторого числа удовлетворяющих условию задачи, наибольшие слагаемые которых различны. Пусть в одном наибольшее слагаемое это а в другом Тогда, согласно утверждению, хотя  – противоречие.

Существование представления практически очевидно. Если то возьмем в представление слагаемое а дальше рекурсивно построим представление для Ясно, что поэтому наибольшее слагаемое его представления не превосходит поэтому полученное представление для тоже удовлетворяет условию задачи.