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.