Числа Фибоначчи

Так называют числа, рекуррентное определение которых задается равенствами

Первые двенадцать чисел Фибоначчи таковы

Образуем производящую функцию

Тогда

Отсюда и

В этой функции как в одном мешке скрыта вся последовательность чисел Фибоначчи. В частности, . Однако мы пойдем другим путем. Представим в виде . Тогда числа обратны корням квадратного уравнения и тем самым есть корни уравнения . Его корни суть

Тогда, применяя формулу суммы геометрической прогрессии, получим:

Как итог, получаем явную формулу

Системой счисления Фибоначчи называется представление натурального числа в виде суммы чисел Фибоначчи

(здесь и далее )

ТЕОРЕМА 3. Представление вида (9) существует и единственно.

Доказательство. Используем «жадный» алгоритм представления. Выбираем максимальное такое, что . Если здесь равенство, то разложение (9) построено. Иначе выбираем максимальное такое, что и т. д. Заметим, что так как в противном случае и – противоречие с максимальностью . Понятно, что этот процесс оборвется на конечном шаге.

Единственность. Из рекуррентного задания чисел Фибоначчи следует, что

.

Отсюда просто следует единственность числа , а затем применяем индукцию к . □