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

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


 \texttt L(n):=  \\\texttt \{begin\{cases\}\\\texttt   1               \& \{text\{если \} n = 0; \{\{\\\texttt   1               \& \{text\{если \} n = 1; \{\{\\\texttt   L(n-1)+L(n-2)+1 \& \{text\{если \} n \textgreater 1. \{\{\\\texttt  \{end\{cases\}\\
 Эдсгер Дейкстра использовал их как составную часть своего алгоритмаплавной сортировки, и изучил их некоторые особенности.

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


 Числа Леонардо связаны с числами Фибоначчи черезформулуL(n)=2F(n+1)1,n0.
 Из этой формулы прямо следует выражение для чисел Леонардо, аналогичноеформуле Бине для чисел Фибоначчи:

L(n)=2φn+1(1φ)n+1φ(1φ)1=25(φn+1(1φ)n+1)1
 где φ=(1+5)/2 является золотым сечением, и кроме тогоφ и 1φ=(15)/2 являются корнями квадратногоуравнения x2x1=0.
 Первые двадцать членов последовательности чисел Леонардо таковы:

 1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, 287, 465, 753, 1219, 1973,3193, 5167, 8361, 13529 —