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

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


  \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 —