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

В этой статье слишком много ссылок на первоисточники . Пожалуйста, улучшите это, добавив вторичные или третичные источники . ( Июль 2017 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

Эти номера Leonardo представляют собой последовательность чисел , данные рецидива:

${\ displaystyle L (n) = {\ begin {cases} 1 & {\ mbox {if}} n = 0 \\ 1 & {\ mbox {if}} n = 1 \\ L (n-1) + L (n -2) +1 & {\ mbox {if}} n> 1 \\\ end {case}}}$

Дейкстра ^[1] использовали их в качестве составной части его Плавная сортировка алгоритма , ^[2] , а также проанализировали их в некоторых деталях. ^[3]

Ценности [ править ]

Первые несколько чисел Леонардо

${\displaystyle 1,\;1,\;3,\;5,\;9,\;15,\;25,\;41,\;67,\;109,\;177,\;287,\;465,\;753,\;1219,\;1973,\;3193,\;5167,\;8361,\ldots }$(последовательность A001595 в OEIS )

Связь с числами Фибоначчи [ править ]

Числа Леонардо связаны с числами Фибоначчи соотношением .${\displaystyle L(n)=2F(n+1)-1,n\geq 0}$

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

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

где золотое сечение и - корни квадратного многочлена .${\displaystyle \varphi =\left(1+{\sqrt {5}}\right)/2}$${\displaystyle \psi =\left(1-{\sqrt {5}}\right)/2}$ ${\displaystyle x^{2}-x-1=0}$

Ссылки [ править ]

Внешние ссылки [ править ]

• Последовательность OEIS A001595