Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

marked as duplicate by J. M., Martin Sleziak, Asaf Karagila, Jonas Meyer, Henning Makholm Nov 28 '11 at 0:59

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

3  
+1 for being very explicit on what you did. –  Patrick Da Silva Nov 26 '11 at 23:26
    
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

4 Answers 4

up vote 3 down vote accepted

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.

share|improve this answer
    
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$.

share|improve this answer
    
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,

share|improve this answer
1  
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.

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.