.
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 * \left( \frac{\varphi^{(n+1)} - (1-\varphi)^{(n+1)}}{\varphi - (1-\varphi)} \right) - 1 = \left( \frac{2}{\sqrt 5} \right) * (\varphi^{(n+1)} - (1-\varphi)^{(n+1)}) - 1 \)
where \( \varphi=(1+\sqrt 5)/2 \) is the golden ratio, and \( \varphi \) and \( 1-\varphi=(1-\sqrt 5)/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
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
