Числа Леонардо

Числа Леонардо — послідовність чисел, задається залежністю:

${\displaystyle L(n):={\begin{cases}1&{\text{при }}n=0;\\1&{\text{при }}n=1;\\L(n-1)+L(n-2)+1&{\text{при }}n>1.\\\end{cases}}}$ 

Едсгер Дейкстра використовував їх як складову частину свого алгоритму плавного сортування, та вивчив їх деякі властивості.

Взаємозв'язок з числами Фібоначчі

Числа Леонардо пов'язані з числами Фібоначчі за формулою: ${\displaystyle L(n)=2F(n+1)-1,n\geqslant 0}$.

З цієї формули прямо випливає вираз для чисел Леонардо, аналогічний формулі Біне для чисел Фібоначчі:

${\displaystyle L(n)=2{\frac {\varphi ^{n+1}-(1-\varphi )^{n+1}}{\varphi -(1-\varphi )}}-1={\frac {2}{\sqrt {5}}}\left(\varphi ^{n+1}-(1-\varphi )^{n+1}\right)-1}$,

де ${\displaystyle \varphi =(1+{\sqrt {5}})/2}$ є золотим перетином, і крім того ${\displaystyle \varphi }$ та ${\displaystyle 1-\varphi =(1-{\sqrt {5}})/2}$ є коренями квадратного рівняння ${\displaystyle x^{2}-x-1=0.}$

Члени послідовності

Перші двадцять членів послідовності чисел Леонардо такі:

${\displaystyle 1,\;1,\;3,\;5,\;9,\;15,\;25,\;41,\;67,\;109,\;177,\;287,\;465,\;753,\;1219,\;1973,\;3193,\;5167,\;8361,\ldots }$ послідовність A001595 з Онлайн енциклопедії послідовностей цілих чисел, OEIS

Джерела

• EWD797
• EWD796a