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

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

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

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

Взаємозв'язок з числами Фібоначчі[ред. | ред. код]

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

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

$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$ ,

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

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

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