Leonardo number

From Wikipedia, the free encyclopedia

The Leonardo numbers are a sequence of numbers given by:

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, and also analysed them in some detail.[2]

They are related to the Fibonacci numbers by the relation L(n) = 2\times F(n+1) - 1 (following the convention that F(0) = 0).

[edit] References

  1. ^ EWD797
  2. ^ EWD796a

[edit] External links