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

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

$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]

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

Числа Леонардо связаны с числами Фибоначчи через формулу$L(n) = 2 * F(n+1) - 1, n \ge 0$.

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

$L(n) = 2 * \left( \frac{\varphi^{(n+1)} - (1-\varphi)^{(n+1)}}{\varphi - (1-\varphi)} \right) - 1 = \left( \frac{2}{\sqrt 5} \right) * (\varphi^{(n+1)} - (1-\varphi)^{(n+1)}) - 1$

где $\varphi=(1+\sqrt 5)/2$ является золотым сечением, и кроме того $\varphi$ и $1-\varphi=(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, \ldots$ последовательность A001595 в OEIS

Примечания

1. ↑ EWD797
2. ↑ EWD796a