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]

Computing a second-order recurrence relation recursively and without memoization requires L(n) computations for the n-th item of the series.

Relation to Fibonacci numbers

The Leonardo numbers are related to the Fibonacci numbers by the relation \( L(n) = 2 F(n+1) - 1, n \ge 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. \)

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 OEIS)

References

EWD797
Dijkstra, Edsger W. Smoothsort – an alternative to sorting in situ (EWD-796a). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (original; transcription)

EWD796a

External links

"Sloane's A001595 ", The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.

1 Rising and falling factorials
2 Identities and relations
3 Table of values
4 See also

Mathematics Encyclopedia