Leonardo number

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

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

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

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 $\varphi =\left(1+{\sqrt {5}}\right)/2$ and $\psi =\left(1-{\sqrt {5}}\right)/2$ are the roots of the quadratic polynomial $x^{2}-x-1=0$ .