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

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

$L\; (n)\; =\; \{1,\; если\; n\; =\; 0,\; 1,\; если\; n\; =\; 1,\; L\; (n\; -\; 1)\; +\; L\; (n\; -\; 2)\; +\; 1\; если\; n>1\; \{\backslash \; displaystyle\; L\; (n)\; =\; \{\backslash \; begin\; \{cases\}\; 1\; \{\backslash \; t\_dv\; \{if\}\}\; n\; =\; 0\; \backslash \backslash \; 1\; \{\backslash \; t\_dv\; \{if\}\}\; n\; =\; 1\; \backslash \backslash \; L\; (n-1)\; +\; L\; (n-2)\; +1\; \{\backslash \; t\_dv\; \{if\}\}\; n>1\; \backslash \backslash \backslash \; end\; \{case\}\}\}$

Эдсгер В. Дейкстра использовал их как неотъемлемую часть его smoothsort алгоритм, а также проанализировал их довольно подробно.

• 1 Значения
• 2 Связь с числами Фибоначчи
• 3 Ссылки
• 4 Внешние ссылки

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

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

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

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

$L\; (N)\; знак\; равно\; 2\; \phi \; N\; +\; 1\; -\; \psi \; N\; +\; 1\; \phi \; -\; \psi \; -\; 1\; =\; 2\; 5\; (\phi \; N\; +\; 1\; -\; \psi \; n\; +\; 1)\; -\; 1\; =\; 2\; F\; (n\; +\; 1)\; -\; 1\; \{\backslash \; Displaystyle\; L\; (\; n)\; =\; 2\; \{\backslash \; frac\; \{\backslash \; varphi\; ^\; \{n\; +\; 1\}\; -\; \backslash \; psi\; ^\; \{n\; +\; 1\}\}\; \{\backslash \; varphi\; -\; \backslash \; psi\}\}\; -\; 1\; =\; \{\backslash \; frac\; \{2\}\; \{\backslash \; sqrt\; \{5\}\}\; \}\; \backslash \; l\; eft\; (\backslash \; varphi\; ^\; \{n\; +\; 1\}\; -\; \backslash \; psi\; ^\; \{n\; +\; 1\}\; \backslash \; right)\; -1\; =\; 2F\; (n\; +\; 1)\; -1\}$

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

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