Leonardo number

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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

Edsger W. Dijkstra[1] used them as an integral part of his smoothsort algorithm,[2] and also analyzed them in some detail.[3]

Values[edit]

The first few Leonardo numbers are

(sequence A001595 in the OEIS)

Relation to Fibonacci numbers[edit]

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 .

References[edit]

External links[edit]