math Common summations in computer science Sums of Fibonacci Numbers
Example
The Fibonacci numbers are defined inductively as
- F0 = 0
- F1 = 1
- Fn+2 = Fn + Fn+1
The sum of the first n+1 Fibonacci numbers is given by
F0 + F1 + F2 + ... + Fn = Fn+2 - 1.
This summation arises, among other places, in the analysis of Fibonacci heaps, where it's used to provide a lower bound on the number of nodes in each tree in the heap.
