Последовательность чисел Фибоначчи получаем немного изменив двоичную систему счисления - проведём преобразование. Пример:


Как будем преобразовывать: нули заменим единицами, единицы двойками, после суммируем их.



Запишем в два столбика числа до преобразования, и после:

;

;

;

;

;

;

;

;

;

;

;

Числа справа повторяются, посчитаем их повторения:

;

;

;

;

;

;

;

;
Получаем последовательность чисел Фибоначчи.
Чтобы вывести формулу для чисел Фибоначчи, нужно посчитать количество повторений числа. Отмечу, каждое повторяющееся число

(преобразованное из двоичного числа) встречается в натуральном ряду у чисел в промежутке

;

;
Для примера возьмём повторяющееся число

. Сколькими способами мы можем записать число

суммой из двоек и единиц?




От каждой из вариантов отнимем по одной двойке:




Для каждого случая высчитаем число сочетаний из

(количества чисел) по

(количество двоек), и суммируем их. Получаем:

В википедии упоминается лишь про диагональное суммирование в треугольнике Паскаля.