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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

 
  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 последовательность A001595 в OEIS

Примечания[править | править вики-текст]