# Fibonacci induction proof?

The Fibonacci Numbers $(f_n)$ are defined $f_1=f_2=1$, and $f_n=f_{n-1}+f_{n-2} ,\,\,\,\forall n \geq2$.

Prove that for every integer $n \geq 1$, $$f_1 +f_2 +···+f_n =f_{n+2}−1$$

• ① The correct HTML representation of subscript is f<sub>1</sub>, the "/" preceeds the "sub" at the end, however ② we support TeX here, you could just write $f_1 = f_2 = 1$ as so on. – kennytm Mar 27 '15 at 9:24
• Welcome to MSE! What have you tried so far? – mrp Mar 27 '15 at 9:31
• meta.math.stackexchange.com/questions/5020/… – Bumblebee Mar 27 '15 at 9:33

As $f_2 = 1$, the conclusion is true for $n = 0$, for the induction suppose $\sum_{k=1}^n f_k = f_{n+2} - 1$ holds for some $n \ge 0$, then we have \begin{align*} \sum_{k=1}^{n+1} f_k &= \sum_{k=1}^n f_k + f_{n+1}\\ &= f_{n+2} - 1 + f_{n+1}\\ &= f_{n+3} - 1 \end{align*}
$$f_n-f_{n-1}=f_{n-2},\,\,\,\,\color{Red}{\text{Telescope}}$$
$f_1 +f_2 +···+f_n =f_{n+2}−1 \to f_1 +f_2 +···+f_n =f_n + f_{n+1}−1$, so:
$f_1 +f_2 +···+f_{n-1} =f_{n+1}−1$.
Repeat until $f_1=f_3-1$, which is true ($f_3=2$).
• $P(n) \to P(n-1)$, so by induction $P(n+1) \to P(n)$ – JonMark Perry Mar 27 '15 at 10:48