The Fibonacci Numbers
We define the \( n \)-th fibonacci number as follows
  • \( F _ 0 = 0 \) and \( F _ 1 = 1 \)
  • \( F _ n = F _ { n - 1 } + F _ { n - 2 } \) for every \( n \ge 2 \)
Sum Equals Jump 2 minus One
For every \( n \in \mathbb{ N } _ 0 \) we have \[ F _ 0 + F _ 1 + \cdots + F _ n = F _ { n + 2 } - 1 \]
We prove it by induction, for the base case \( F \left( 0 + 2 \right) - 1 = \left( F _ 1 + F _ 0 \right) - 1 = 1 + 0 - 1 = 0 = F _ 0 \) as needed. Next assume it holds true for \( k \in \mathbb{ N } _ 0 \) and then we want to prove that \( F _ { k + 3 } - 1 = F _ 0 + \ldots + F _ { k + 1 } \), we can handle the sum with the inductive hypothesis, so that \[ F _ 0 + \ldots + F _ k + F _ { k + 1 } = \left( F _ { k + 2 } - 1 \right) + F _ { k + 1 } = F _ { k + 3 } - 1 \] as needed.