Proof by Induction: Alternating Sum of Fibonacci Numbers 
Possible Duplicate:
Show that $f_0 - f_1 + f_2 - \cdots - f_{2n-1} + f_{2n} = f_{2n-1} - 1$ when $n$ is a positive integer 

This is a homework question so I'm looking to just be nudged in the right direction, I'm not asking for my work to be done for me.  

The Fibonacci numbers are defined as follows: $f_0 = 0$, $f_1 = 1$, and $f_{n+2} = f_n + f_{n+1}$ whenever $n \geq 0$. Prove that when $n$ is a positive integer:
\begin{equation*}
f_0 - f_1 + f_2 + \ldots - f_{2n-1} + f_{2n} = f_{2n-1} - 1
\end{equation*}

So as I understand it, this is an induction problem. I've done the basis step using $n = 1$:  
\begin{align*}
- f_{2(1)-1} + f_{2(1)} &= f_{2(1)-1} - 1\newline
- f_1 + f_2 &= f_1 - 1\newline
- 1 + 1 &= 1 - 1\newline
0 &= 0
\end{align*}
I've concluded that the inductive hypothesis is that $- f_{2n-1} + f_{2n} = f_{2n-1} - 1$ is true for some $n \geq 1$. From what I can gather, the inductive step is:  
\begin{equation*}
f_0 - f_1 + f_2 + \ldots - f_{2n-1} + f_{2n} - f_{2n+1} = f_{2n} - 1
\end{equation*}
However, what I find when I try to prove it using that equation is that it is incorrect. For example, when I take $n = 1$  
\begin{align*}
- f_{2(1)-1} + f_{2(1)} + f_{2(1)+1} &\neq f_{2(1)} - 1\newline
- f_1 + f_2 - f_3 &\neq f_2 - 1\newline
- 1 + 1 - 2 &\neq 1 - 1\newline
-2 &\neq 0
\end{align*}
I suppose that my inductive step is wrong but I'm not sure where I went wrong. Maybe I went wrong elsewhere. Any hints?
 A: Your reasoning is sound, but your induction hypothesis is a bit wrong. It should be something like this:

Assume that it holds for $n = k$. We then have
$$
f_0 -f_1 + \cdots -f_{2k-1} +f_{2k} = f_{2k-1} -1
$$
I will now show that
$$
f_0 -f_1 + \cdots -f_{2k-1} +f_{2k} -f_{2k + 1} + f_{2k + 2} = f_{2k+1} -1
$$

If you solve that, then it will be proven.
A: You get the inductive step by replacing $n$ everywhere with $n+1$. So the alternating sum should go up to $2(n+1)$, not $2n+1$. 
A: You have the inductive step wrong. What you want to prove is that
$$
f_0 - f_1 + f_2 - \dots - f_{2n+1} + f_{2n+2} = f_0 - f_1 + f_2 - \dots - f_{2(n+1)-1} + f_{2(n+1)} = f_{2(n+1)-1} - 1 = f_{2n+1} - 1.
$$
Perhaps it will be easier to prove something that's true. =D
Hope that helps,
A: HINT $\ $ LHS,RHS both satisfy $\rm\ g(n+1) - g(n)\: =\: f_{2\:n},\ \ g(1) = 0\:.\:$ But it is both short and easy to prove by induction that the solutions $\rm\:g\:$  of this recurrence are unique. Therefore LHS = RHS.
Note that abstracting away from the specifics of the problem makes the proof both much more obvious and, additionally, yields a much more powerful result - one that applies to any functions satisfying a recurrence of this form. Generally uniqueness theorems provide very powerful tools for proving equalities. For much further elaboration and many examples see my prior posts on telescopy and the fundamental theorem of difference calculus, esp. this one.
