Solution

Conjecture and prove a formula for the sum of the first $n$ Fibonacci numbers.


Letting $F_i$ denote the $i^{th}$ Fibonacci number (where $F_0 = F_1 = 1$), we might conjecture that

$$\sum_{i=0}^n F_i = F_{n+2} - 1$$

We can establish this result via induction.

First note that when $n=0$, the left side above is simply $\sum_{i=0}^n F_i = F_0 = 1$, while the right side evaluates to and $F_2 - 1 = 2 - 1 = 1$. As these agree in value, our basis step is complete.

Then, to proceed with the inductive step -- we need to show that if $\sum_{i=0}^k F_i = F_{k+2} - 1$, then $\sum_{i=0}^{k+1} F_i = F_{k+3} - 1$. To this end, consider the following:

$$\begin{array}{rcl} \sum_{i=0}^{k+1} F_i &=& \left[ \sum_{i=0}^k F_i \right] + F_{k+1}\\\\ &=& (F_{k+2} - 1) + F_{k+1}\\\\ &=& (F_{k+2} + F_{k+1}) - 1\\\\ &=& F_{k+3} - 1 \end{array}$$

Therefore by the principle of mathematical induction, the following holds for integer values of $n \ge 0$:

$$\sum_{i=0}^n F_i = F_{n+2} - 1$$