Mathematical induction with the Fibonacci sequence

Question

Let $F_n$ be the Fibonacci sequence: $$ F_0 = 0,\ F_1 = 1 \\ F_n = F_{n−1} + F_{n−2}, n \geq 2 $$

Use mathematical induction to prove that for all positive integers $n$, $$\sum_{i=0}^n (-1)^i \cdot F_i = (-1)^n \cdot F_{n-1} - 1$$

I understand the steps involving the base case, assuming the statement true for $n=k$ and then trying to prove that it's true for $n=k+1$. I am in the process of the actual induction and I'm trying to use the appropriate definitions to simplify my statement. It's not working out.

$\sum_{i=0}^{k+1} (-1)^i(F_{i}) = (\sum_{i=0}^k (-1)^i(F_{i}))+(-1)^{k+1}*F_{k}-1$

$(-1)^k(F_{k-1})+(-1)^{k+1}(F_{k})-1$

$(-1)^k(F_{k-1})+(-1)(-1)^k(F_{k})-1$

$(-1)^k(F_{k-1}-F_{k})-1$

$(-1)^k(-1)(F_{k}-F_{k-1})-1$

$(-1)^{k+1}(F_{k}-F_{k-1})-1$

$(-1)^{k+1}(F_{k-2})-1$ (by the definition $F_{n}=F_{n-1}+F_{n-2}$)

I feel like I'm close to the pattern that I'm supposed to identify here, but the only part that doesn't match the original is the Fsub(k-2). It needs to be just Fsub(k), but I haven't been able to manipulate the algebra in a way that yields Fsub(k).

Answer 1

Here's how to do it.

Assume that $\sum_{i=0}^n (-1)^i F_i = (-1)^n F_{n-1} - 1 $.

You want to show that $\sum_{i=0}^{n+1} (-1)^i F_i = (-1)^{n+1} F_{n} - 1 $.

Note that this is just the assumption with $n$ replaced by $n+1$.

$\begin{array}\\ \sum_{i=0}^{n+1} (-1)^i F_i &=\sum_{i=0}^{n} (-1)^i F_i+(-1)^{n+1}F_{n+1} \qquad\text{(split off the last term)}\\ &=(-1)^n F_{n-1} - 1+(-1)^{n+1}F_{n+1} \qquad\text{(this was assumed)}\\ &=(-1)^{n+1}F_{n+1}+(-1)^n F_{n-1} - 1\\ &=(-1)^{n+1}(F_{n+1}- F_{n-1}) - 1\\ &=(-1)^{n+1}F_{n} - 1 \qquad\text{(since }F_{n+1}- F_{n-1}=F_{n})\\ \end{array} $

And we are done.

Answer 2

Also, since $F_{k+1}=F_k+F_{k-1}$, we have $\displaystyle\sum_{i=0}^{k+1}(-1)^iF_i=(-1)^kF_{k-1}-1+(-1)^{k+1}F_{k}+(-1)^{k+1}F_{k-1}$. Since $k$ and $k+1$ are consecutive, one will be even and the other odd, so $(-1)^{k}+(-1)^{k+1}=0$, and the terms cancel.