Solution: Last Digit of the Sum of Fibonacci Numbers

Solution 1: Pisano period

The table below shows the first 11 Fibonacci numbers and the first 11 numbers $S_n = F_0 +F_1 +\cdot \cdot \cdot+F_n$.

Stop and think: Do you see any similarities between sequences $F_0,\ldots,F_{10}$ and $S_0,\ldots,S_{10}$?

It looks like $S_n=F_{n+2}-1$. Let’s prove it by induction. This condition certainly holds for the base step $(n = 0)$ since $S_0 = F_2 - 1$. For the induction step, let’s assume that the statement holds for $0,1,\cdot \cdot \cdot,n$ and prove it for $n+1$:

$S_{n+1}=F_0+F_1+\cdot \cdot \cdot+F_n+F_{n+1}=S_n+F_{n+1}=F_{n+2}-1+F_{n+1}=F_{n+3}-1$.

Another way of arriving at the formula $S_n = F_{n+2} - 1$ is to sum up the following equalities:

$$\begin{aligned}&F_{n} &= ~~&F_{n+2} - \color{blue}{F_{n+1}}\\ &F_{n-1} &= ~~&\color{blue}{F_{n+1}} - \color{red}{F_{n}}\\ &F_{n-2} &= ~~&\color{red}{F_{n}} - F_{n-1}\\ && \vdots\\ &F_{2} &= ~~&F_{4} - \color{green}{F_{3}}\\ &F_{1} &= ~~&\color{green}{F_{3}} - \color{red}{F_{2}}\\ &F_{0} &= ~~&\color{red}{F_{2}} - F_{1} \end{aligned}$$

Since the identically colored terms cancel out, the sum of all terms on the left is $S_n$ ...