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.

I have the following theorem to prove by induction:

$$ F_{n} \cdot F_{n+1} - F_{n-2}\cdot F_{n-1}=F_{2n-1} $$

It is mentioned in my script that the proof should be possible only by using the recursion of Fibonacci numbers:$$F_{n+1}=F_{n}+F_{n-1}$$

I was only able to proof this theorem by using other theorems, as I was not able to proof it without knowing an relationship between $F_{n }$ and $F_{2n}$. The thing is: I know that the theorem is true, and I have 2 different proofs for it, but I am searching for an elegant proof without using other knowledge apart from the recursion.

Induction hypothesis: $$ F_{n} \cdot F_{n+1} - F_{n-2}\cdot F_{n-1}=F_{2n-1} $$ We want to show the following is also true:

$$ F_{n+1} \cdot F_{n+2} - F_{n-1}\cdot F_{n}=F_{2n+1} $$

So we transform the induction hypothesis by adding $F_{n+1}^2-F_{n-1}^2$:

$$ F_{n} \cdot F_{n+1} +F_{n+1}^2 - F_{n-2}\cdot F_{n-1} -F_{n-1}^2 = F_{n+1} \cdot F_{n+2} - F_{n-1}\cdot F_{n}=F_{2n-1} + F_{n+1}^2-F_{n-1}^2$$

So we have the LHS of what we want to show. We would need to show that $F_{n+1}^2-F_{n-1}^2=F_{2n}$ and our proof would be finished. I was not able to proof this, I tried it with another induction.

Another idea was to use two induction hypothesis: $$ (1) F_{n-1} \cdot F_{n} - F_{n-3}\cdot F_{n-2}=F_{2n-3} $$ $$ (2) F_{n} \cdot F_{n+1} - F_{n-2}\cdot F_{n-1}=F_{2n-1} $$

and then $(2)-(1)= F_{n-2}$ would give us: $$ F_{2n-2}= F_{n}^2-F_{n-2}^2$$ This looks more promising, considering our problem in the last attempt. By adding (2) we get: $$ F_{2n}= F_{n} \cdot F_{n+2} - F_{n-2}\cdot F_{n}$$ By adding (2) again we would get: $$ F_{2n+1}= F_{n} \cdot F_{n+3} - F_{n-2}\cdot F_{n+1}$$ Now one would need to show this is equivalent, to what we want to prove. Again I was not successful trying to do this.

I would be very glad if someone could show me an complete induction proof not requiring other theorems. I know this theorem is only a special case of the following: $$ F_{n+m} = F_{n−1}\cdot F_{m} + F_{n}\cdot F_{m+1}$$, which in fact is easy to show with induction. But I only know this theorem from googeling and I don't think it is necessary to do an induction proof of my special case of the theorem only by assuming the general case.

I hope someone would like to help me!

share|improve this question
    
Do you have $F_0 = F_1 = 1$ or $F_1 = F_2 = 1$? –  Arthur May 4 '13 at 12:13
1  
I have $F_0=0 $ and $F_1=1$ whichs means $F_1=F_2=1$ –  GEO May 4 '13 at 12:20

2 Answers 2

up vote 2 down vote accepted

You can apply induction to $F_{2n}$ simultaneously:

$$ \begin{align} F_{2n} &= F_{2n-1}+F_{2n-2} \\ &=F_nF_{n+1}-F_{n-2}F_{n-1}+F_n^2-F_{n-2}^2 \\ &=F_nF_{n+2}-F_nF_{n-2} \\ &= F_n(F_{n+2}-F_{n-2}) \\ &= (F_{n+1}-F_{n-1})(F_{n+1}+F_{n-1}) \\ &=F_{n+1}^2-F_{n-1}^2\;. \end{align} $$

share|improve this answer
    
Thank you very much sir! –  GEO May 4 '13 at 14:18

The following reasoning proves $F_{2n} = F_{n+1}^2-F_{n-1}^2$, which would prove your first induction hypothesis

$$ F_{2n} = F_{2n-1} + F_{2n-2} = 2F_{2n-2} + F_{2n-3} = 3F_{2n-3} + 2F_{2n-4}=5F_{2n-4} + 3F_{2n-5} \\\\ \vdots\\\\ = F_{i+1}\cdot F_{2n-i} + F_{i}\cdot F_{2n-i-1} $$ Specifically, for $i=n-1$, we have that $F_{2n} = F_{n}F_{n+1} + F_{n}F_{n-1}$. We now only need to check that $$ F_{n}F_{n+1} + F_{n}F_{n-1} = (F_{n+1}-F_{n-1})F_{n+1} + F_{n}F_{n-1} = F_{n+1}^2 - F_{n+1}F_{n-1} + F_nF_{n-1} \\\\ = F_{n+1}^2 - (F_n + F_{n-1})F_{n-1} + F_nF_{n-1} = F_{n+1}^2 - F_{n-1}^2 $$ and we are done.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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