Числа Фибоначчи в двоичной системе счисления

[Soul Friend]

Последовательность чисел Фибоначчи получаем немного изменив двоичную систему счисления - проведём преобразование. Пример:
$(n)_{notation}$
$(5)_{10}=(101)_2$
Как будем преобразовывать: нули заменим единицами, единицы двойками, после суммируем их. $101\rightarrow 212 \rightarrow 5$
$(6)_{10}=(011)_2 \rightarrow 122 \rightarrow 5$
$(7)_{10}=(111)_2=\rightarrow 222 \rightarrow 6$
Запишем в два столбика числа до преобразования, и после:
$0\rightarrow 1$ ; $1\rightarrow 2$ ; $2\rightarrow3$ ; $3\rightarrow4$ ; $4\rightarrow4$ ; $5\rightarrow5$ ; $6\rightarrow5$ ; $7\rightarrow6$ ; $8\rightarrow5$ ; $9\rightarrow6$ ; $10\rightarrow6$ ; $11\rightarrow7$
Числа справа повторяются, посчитаем их повторения:
$1\rightarrow1$ ; $2\rightarrow1$ ; $3\rightarrow1$ ; $4\rightarrow2$ ; $5\rightarrow3$ ; $6\rightarrow5$ ; $7\rightarrow8$ ; $8\rightarrow13$ ;
Получаем последовательность чисел Фибоначчи.
Чтобы вывести формулу для чисел Фибоначчи, нужно посчитать количество повторений числа. Отмечу, каждое повторяющееся число $n$ (преобразованное из двоичного числа) встречается в натуральном ряду у чисел в промежутке $\min=floor(\left \frac{n+1}{2})\right $ ; $\max=2^{n-1}$ ;
Для примера возьмём повторяющееся число $8$ . Сколькими способами мы можем записать число $8$ суммой из двоек и единиц?
$1+1+1+1+1+1+2$
$1+1+1+1+2+2$
$1+1+2+2+2$
$2+2+2+2$
От каждой из вариантов отнимем по одной двойке:
$1+1+1+1+1+1$
$1+1+1+1+2$
$1+1+2+2$
$2+2+2$
Для каждого случая высчитаем число сочетаний из $n$ (количества чисел) по $k$ (количество двоек), и суммируем их. Получаем:

$$\sum_{k=0}^{floor (\left \frac{n-2}{2} )\right } ( \frac{(n-(k+2))!}{(n-(2k+2))! \cdot k!} )$$

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

[Dmitriy40]

Soul Friend в сообщении #1264766 писал(а):

$(6)_{10}=(011)_2$

Более общеупотребительным является запись старшего значащего бита слева, а не справа. И шестёрка выглядит соответственно наоборот: $6_{10}=110_2$.

-- 12.11.2017, 18:10 --

Soul Friend в сообщении #1264766 писал(а):

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

Это преобразование можно упростить (для понимания): к количеству единиц в двоичной записи добавить длину двоичной записи числа. Или удвоить количество единиц и добавить количество нулей.

-- 12.11.2017, 18:13 --

И что предлагается обсуждать то?

[Andrey A]

Soul Friend в сообщении #1264766 писал(а):

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

Именно диагональное суммирование по Вашей формуле и получаем. Только для $F_{n-1}$. А что даёт двоичная запись, я тоже не понял.

[Soul Friend]

Странное проявление (или выявление) последовательности, необычная математическая логика. Хотя, есть и другие формулы для чисел Фибоначчи.

[Andrey A]

Да, есть формула Бине. Увязать двоичную запись с биномиальными коэффициентами можно еще исходя из того факта, что сумма элементов $n$-ой строки треугольника Паскаля есть $n$-ая степень двойки. Из двоичной записи получаем нужный набор строк, но такое суммирование годится не только для фибоначчи.

[arseniiv]

Soul Friend в сообщении #1264766 писал(а):

Числа справа повторяются, посчитаем их повторения:
$1\rightarrow1$ ; $2\rightarrow1$ ; $3\rightarrow1$ ; $4\rightarrow2$ ; $5\rightarrow3$ ; $6\rightarrow5$ ; $7\rightarrow8$ ; $8\rightarrow13$ ;

Тогда правильнее будет считать, что 1 повторяется 0 раз. И в самом деле, если считать ноль представимым пустой строкой, так и будет (мы же не добавляем слева нули к представлениям других чисел, так и для нуля нечего).