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

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

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

Эдсгер Дейкстра использовал их как составную часть своего алгоритма плавной сортировки, и изучил их некоторые особенности.

Взаимосвязь с числами Фибоначчи

Числа Леонардо связаны с числами Фибоначчи через формулу$L(n)=2F(n+1)-1,n⩾0$.

Из этой формулы прямо следует выражение для чисел Леонардо, аналогичное формуле Бине для чисел Фибоначчи:

$L(n)=2\frac{{\phi }^{n+1}-(1-\phi {)}^{n+1}}{\phi -(1-\phi )}-1=\frac{2}{\sqrt{5}}({\phi }^{n+1}-(1-\phi {)}^{n+1})-1$

где $\phi =(1+\sqrt{5})/2$ является золотым сечением, и кроме того $\phi$ и $1-\phi =(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, 13529 —

Шаблон:OEIS

Отношение соседних чисел Леонардо, так же, как и соседних чисел Фибоначчи, стремится к золотому сечению.