Suvarna Garge (Editor)

Leonardo number

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

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

Contents

L ( n ) = { 1 if  n = 0 1 if  n = 1 L ( n − 1 ) + L ( n − 2 ) + 1 if  n > 1

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

1 , 1 , 3 , 5 , 9 , 15 , 25 , 41 , 67 , 109 , 177 , 287 , 465 , 753 , 1219 , 1973 , 3193 , 5167 , 8361 , … (sequence A001595 in the OEIS)

Relation to Fibonacci numbers

The Leonardo numbers are related to the Fibonacci numbers by the relation L ( n ) = 2 F ( n + 1 ) − 1 , n ≥ 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 φ n + 1 − ψ n + 1 φ − ψ − 1 = 2 5 ( φ n + 1 − ψ n + 1 ) − 1 = 2 F ( n + 1 ) − 1

where the golden ratio φ = ( 1 + 5 ) / 2 and ψ = ( 1 − 5 ) / 2 are the roots of the quadratic polynomial x 2 − x − 1 = 0 .

References

Leonardo number Wikipedia
(Text) CC BY-SA