Leonardo number

The Leonardo numbers are a sequence of numbers given by the recurrence:

${\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{cases}}}$

Edsger W. Dijkstra[1] used them as an integral part of his smoothsort algorithm,[2] and also analyzed them in some detail.[3]

Values

The first few Leonardo numbers are

${\displaystyle 1,\;1,\;3,\;5,\;9,\;15,\;25,\;41,\;67,\;109,\;177,\;287,\;465,\;753,\;1219,\;1973,\;3193,\;5167,\;8361,\ldots }$ (sequence A001595 in the OEIS)

Relation to Fibonacci numbers

The Leonardo numbers are related to the Fibonacci numbers by the relation ${\displaystyle L(n)=2F(n+1)-1,n\geq 0}$.

From this relation it is straightforward to derive a closed-form expression for the Leonardo numbers, analogous to Binet's formula for the Fibonacci numbers:

${\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}$

where the golden ratio ${\displaystyle \varphi =\left(1+{\sqrt {5}}\right)/2}$ and ${\displaystyle \psi =\left(1-{\sqrt {5}}\right)/2}$ are the roots of the quadratic polynomial ${\displaystyle x^{2}-x-1=0}$.

References

1. "E.W.Dijkstra Archive: Fibonacci numbers and Leonardo numbers. (EWD 797)". www.cs.utexas.edu. Retrieved 2020-08-11.
2. Dijkstra, Edsger W. Smoothsort – an alternative to sorting in situ (EWD-796a) (PDF). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (transcription)
3. "E.W.Dijkstra Archive: Smoothsort, an alternative for sorting in situ (EWD 796a)". www.cs.utexas.edu. Retrieved 2020-08-11.

External links

• OEIS sequence A001595