Leonardo number


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.

Values

The first few Leonardo numbers are

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.