WikiSort.ru - Не сортированное

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

${\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}}}$

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

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

Числа Леонардо связаны с числами Фибоначчи через формулу${\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.}$

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

1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, 287, 465, 753, 1219, 1973, 3193, 5167, 8361, 13529 — последовательность A001595 в OEIS

Примечания

Это заготовка статьи по математике. Вы можете помочь проекту, дополнив её.