Basic Discrete Mathematics Recurrence question Good afternoon,
I've been assigned the following problem from my Intro to Discrete Mathematics:
Show that  $\sum_{i=1}^n$ F(i) = F(n+2) - 1
note: F(n) is the nth term in the fibonacci sequence.
I've tried to do it through an expand, guess, verify, method but I just can't figure out how to relate the left side to the right side. Can someone walk me through this?
Thanks in advance
 A: We can do this through a proof by induction.
Remember, $F(1) = 1, F(2) = 1, F(3) = F(1) + F(2) = 2, \dots F(k) = F(k-1)+F(k-2)$
We can show that the formula is true for $n=1$:
$\sum\limits_{i=1}^{1}$ F(i) = F(1) = F(1+2) - 1 = 1
Now, assume for some value n,
$\sum\limits_{i=1}^{n} F(i) = F(n+2) - 1$
Then for n+1, we have $\sum\limits_{i=1}^{n+1} F(i) = F(n+2) - 1 + F(n+1)$
However, by definition of the Fibonacci sequence, $F(n+1) + F(n+2) = F(n+3)$. Therefore, we have:
$$\sum\limits_{i=1}^{n+1} F(i) = F(n+3) - 1 = F([n+1]+2) - 1$$
Now we have shown that if the formula is true for $n$, it must be true for $n+1$, and we have shown it to be true for $n=1$. By the principle of mathematical induction, we know that for all $n\geq 1$, the formula is true.
A: Use $F(k+1) = F(k) + F(k-1)$ for k > 1, do a sum
$$\sum_{i = 1}^n F(i +1) = \sum_{i = 1}^n F(i) + \sum_{i = 1}^n F(i -1)$$
Now, $$LHS = F(n + 1) + \sum_{i = 1}^n F(i) - F(1)$$
$$RHS=\sum_{i = 1}^n F(i) + \sum_{i = 1}^n F(i) - F(n) + F(0)$$
Let $S_n = \sum_{i = 1}^n F(i)$, the equation becomes
$$S + F(n+1) - F(1)= 2S -F(n) + F(0)$$
Solve it for S
$$S = F(n+1)+F(n) - F(0) - F(1) = F(n + 2) - F(0)- F(1)$$
A: Let's look carefully at a specific case that may give a general idea.  At each step, except the last, we'll expand the leftmost term.  In the last step we'll use that $F(2)=1$.
$$\begin{array}{lcr} F(6)&=&F(5)+F(4)\\&=&F(4)+F(3)+F(4)\\&=&F(3)+F(2)+F(3)+F(4)\\&=&F(2)+F(1)+F(2)+F(3)+F(4)\\ &=& 1+F(1)+F(2)+F(3)+F(4)\end{array}$$
A: $$\begin{align}
F(i)+F(i+1)&=F(i+2)&&\text{(Fibonacci definition)}\\\\
\Rightarrow F(i)&=F(i+2)-F(i+1)\\
\sum_{i=1}^n F(i)&=\sum_{i=1}^n F(i+2)-F(i+1)\\
&=F(n+2)-\underbrace{F(2)}_{=1}&&\text{(by telescoping)}\\
&=F(n+2)-1\qquad\blacksquare\\
\end{align}$$
