Последовательность Леонардо и представление чисел

[Alik]

Последовательность Леонардо задается реккурентным соотношением: $L_n=L_{n-1}+L_{n-2}+1$, и похожа на последовательность Фибоначчи. В частности, при начальных условиях $L_1=L_2=0$ получим $L_n=F_n-1$. В каталоге Sloane это последовательность http://oeis.org/A000071.
Интуиция, а также Brown's criterion подсказывают, что любое целое положительное число может быть представленно в виде суммы различных чисел Леонардо. Следующий вопрос - единственно ли такое представление? Из формулы $L_n=L_{n-1}+L_{n-2}+1$ можно предположить, что оно не будет содержать двух единиц подряд и единицу справа от них на произвольном расстоянии. Таким образом, нужно сформулировать и доказать аналог Zeckendorf's theorem.

[Хорхе]

Alik в сообщении #500945 писал(а):

Следующий вопрос - единственно ли такое представление? Из формулы $L_n=L_{n-1}+L_{n-2}+1$

Вот Вы сами на свой вопрос и ответили. Поскольку $1$ является членом данной последовательности, данная формула недвузначно намекает, что представление не единственно, и за примером далеко ходить не надо: $1+2+4=7$.
(К слову, если б оно было единственно, члены последовательности росли бы не медленнее степеней двойки, что не так.)

[Alik]

То, что для одного и того же числа могут быть несколько представлений понятно. Так, например, для $x=L_n$ их будет по крайней мере два:

01100...001
10000...000 

Однако, есть такие числа для которых существует одно и только одно представление. Можно предположить, что оно совпадает с некоторым каноническим представлением для всех остальных чисел. Нужно понять как это каноническое представление построено.

[Хорхе]

Ну что сказать. Успехов в понимании!

[Alik]

За пожелание - спасибо. Как выяснилось, на эту тему существует статья, и все предыдущие вопросы сводятся к ее пониманию. Такое чувство, что автор хотел запутать врага:
D.E. Daykin, "Representation of natural numbers as sums of generalised Fibonacci numbers - II," The Fibonacci Quarterly, Vol. 7, no.5, 1969
http://www.fq.math.ca/Scanned/7-5/daykin2.pdf
Итак, первые прикидки. Легко показать, что $L_{n+1}=L_n+L_{n-2}+L_{n-4}+...+L_1+n$. Таким образом, если для представления $N$ применить алгоритм последовательного вычитания, он даст код $1010...101$. Это первая часть марлезонского балета. Теперь нужно разобраться с хвостом $n$. Он, очевидно, накапливается и дает арифметическую прогрессию $1+2+3+...+n'$. Пусть ее сумма равна $s$, которую нужно добавить к полученному коду. Отсюда вывод - вид канонического представления зависит от резолюции числа $N$...

[Alik]

Итак, в статье Дайкина обобщенные $(h, k)$ числа Фибоначчи определены для $h\leqslant k \leqslant h+1$ как:

$ u_n=\begin{cases} n & \text{ if } 1 \leqslant n\leqslant k \\ u_{n-1}+u_{n-h} & \text{ if } k<n<h+k \\ u_{n-1}+u_{n-k}+(k-h) & \text{ if } n\geqslant h+k \end{cases} $

В частности, для $k=h=2$ получим обычные числа Фибоначчи, а для $k=2$ и $h=1$ числа Леонардо:

$ F_n=\begin{cases} 1,\: 2\\ 2+1\\ F_{n-1}+F_{n-2} \end{cases} $ и $ L_n=\begin{cases} 1,\: 2\\ L_{n-1}+L_{n-2}+1 \end{cases} $

Если некоторая последовательность $v_n$ представляет собой обобщенные $(h, k)$ числа Фибоначчи, то для натурального $v_{i_d} \leqslant N < v_{i_d+1}$ существует одно и только одно представление в виде:

$N=\sum\limits_{j=1}^{d}v_{i_j}$ где $ \begin{cases} i_2\geqslant i_1+h & \text{ if } d>1 \\ i_{j+1}\geqslant i_j+k & \text{ if } 2 \leqslant j<d \end{cases} $

Из этого, в частности следует, что в представлении Фибоначчи нет двух рядом стоящих единиц. Действительно, подставляя

$i_1=1$ и $k=h=2$ в $ \begin{cases} i_2 = i_1+h \\ i_{j+1}= i_j+k \end{cases} $ последовательно получим $i_j=1,3,5,7,9...$

Для последовательности Леонардо параметры $k=2$ и $h=1$ дают $i_j=1,2,4,6,8...$