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

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

L ( n ) := { 1 если  n = 0 ; 1 если  n = 1 ; L ( n − 1 ) + L ( n − 2 ) + 1 если  n > 1. {displaystyle L(n):={egin{cases}1&{ ext{если }}n=0;1&{ ext{если }}n=1;L(n-1)+L(n-2)+1&{ ext{если }}n>1.end{cases}}}

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

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

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

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

L ( n ) = 2 φ n + 1 − ( 1 − φ ) n + 1 φ − ( 1 − φ ) − 1 = 2 5 ( φ n + 1 − ( 1 − φ ) n + 1 ) − 1 {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} ight)-1}

где φ = ( 1 + 5 ) / 2 {displaystyle varphi =(1+{sqrt {5}})/2} является золотым сечением, и кроме того φ {displaystyle varphi } и 1 − φ = ( 1 − 5 ) / 2 {displaystyle 1-varphi =(1-{sqrt {5}})/2} являются корнями квадратного уравнения x 2 − x − 1 = 0. {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