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

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

 $L (n) : = {\begin{matrix} 1 & при n = 0; \\ 1 & при n = 1; \\ L (n - 1) + L (n - 2) + 1 & при n > 1 . \end{matrix}$

Едсгер Дейкстра використовував їх як складову частину свого алгоритму плавного сортування, та вивчив їх деякі властивості.

Взаємозв'язок з числами Фібоначчі

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

З цієї формули прямо випливає вираз для чисел Леонардо, аналогічний формулі Біне для чисел Фібоначчі:

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

де $φ = (1 + \sqrt{5}) / 2$ є золотим перетином, і крім того $φ$ та $1 - φ = (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, \dots$ Шаблон:OEIS