The Leonardo numbers are a sequence of numbers given by the recurrence:
Edsger W. Dijkstra used them as an integral part of his smoothsort algorithm, and also analyzed them in some detail.
The first few Leonardo numbers are
- (sequence A001595 in the OEIS)
Relation to Fibonacci numbers
The Leonardo numbers are related to the Fibonacci numbers by the relation .
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:
where the golden ratio and are the roots of the quadratic polynomial .