TAOCP 1.2.8 Exercise 20

Exercise 20. [M16] Express $\sum_{k=0}^{n} F_k$ in terms of Fibonacci numbers.

Verified: no
Solve time: -

Solution

We wish to find a closed form for

$$ S_n = \sum_{k=0}^{n} F_k $$

in terms of Fibonacci numbers. We proceed by using the Fibonacci recurrence

$$ F_{k+2} = F_{k+1} + F_k \quad \text{for } k \ge 0. $$

Consider the sum of the first $n+2$ Fibonacci numbers:

$$ \sum_{k=0}^{n+1} F_k = F_0 + F_1 + F_2 + \cdots + F_n + F_{n+1}. $$

We claim that $S_n = F_{n+2} - 1$. To verify this, we proceed by induction on $n$.

Base case ($n=0$):

$$ S_0 = F_0 = 0, \quad F_{0+2}-1 = F_2 - 1 = 1 - 1 = 0. $$

Hence the formula holds for $n=0$.

Induction step: Suppose

$$ S_n = \sum_{k=0}^{n} F_k = F_{n+2} - 1 $$

holds for some $n \ge 0$. Then

\begin{align*}

S_{n+1} &= \sum_{k=0}^{n+1} F_k \

&= \sum_{k=0}^{n} F_k + F_{n+1} \

&= (F_{n+2}-1) + F_{n+1} \quad \text{by the induction hypothesis} \

&= F_{n+1} + F_{n+2} - 1 \

&= F_{n+3} - 1 \quad \text{by the Fibonacci recurrence.}

\end{align*}

Thus the formula holds for $n+1$. By the principle of mathematical induction, the formula holds for all $n \ge 0$.

Therefore, the sum of the first $n+1$ Fibonacci numbers is

$$ \sum_{k=0}^{n} F_k = F_{n+2} - 1. \tag{20} $$

This completes the proof.

∎

We may verify with a small example: for $n=5$, $F_0+\cdots+F_5 = 0+1+1+2+3+5=12$, and $F_7 - 1 = 13-1 = 12$, which agrees.