Proof by Induction: Alternating Sum of Fibonacci Numbers [duplicate]

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?

marked as duplicate by J. M. is a poor mathematician, Martin Sleziak, Asaf Karagila♦, Jonas Meyer, Henning MakholmNov 28 '11 at 0:59

• See also this question: math.stackexchange.com/questions/82140/… – Martin Sleziak Nov 27 '11 at 12:57
• My question was a little more specific, don't you think? I knew it was induction, I just didn't know where I went wrong in my proof. – alexcoco Nov 28 '11 at 3:39

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.

• Thank you. I was originally just adding 1 to the subscript instead of to the $n$. I also didn't realize that I needed to repeat both the $-f_{2k-1}$ and the $f_{2k}$ with the $+1$ to $k$. Your answer helped me find where I was going wrong! – alexcoco Nov 27 '11 at 0:01

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$.

• Thank you very much, I did not notice this – alexcoco Nov 26 '11 at 23:58

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,

• It certainly helps when you try to prove something that's true x) – alexcoco Nov 27 '11 at 0:02

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.