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 am asked to pove the statement about fibonacci sequence. The task is from the passage about series and sequences. But the proof seems to need induction way, doesn't it?

Prove the statement $$F_{n+1}F_{n-1}-(F_{n})^2=(-1)^n$$ for all $n\ge 1$.

How can I prove this by thinking about limit and convergence?

share|improve this question
    
Without induction? –  Nameless Dec 26 '12 at 10:13
1  
Then you seem to have defined $F_n$ without recursion? –  Hagen von Eitzen Dec 26 '12 at 10:19
    
I cannot comprehend, why anybody would want to prove this kind of facts without induction? Induction and recursive definition (such as with Fibonacci sequence) go together like love and marriage. Ok, since you asked, you can probably also do this by using Binet's formula for Fibonacci numbers, but that is a lot messier, and you cannot prove Binet's formula without induction anyway :-) Another point: I don't see any limits or converging sequences here, do you? –  Jyrki Lahtonen Dec 26 '12 at 10:19
    
this is the reason why i asked you guys. $F_{n}$ cannot be defined without recursion, so it is impossible to prove the above statement without induction? –  doniyor Dec 26 '12 at 10:22
1  
Go to page no 8 of this book. You can see the proof. books.google.co.in/… –  Mohan Dec 26 '12 at 10:37

2 Answers 2

up vote 3 down vote accepted

I think this depends on what is meant by "mathematical induction". Recall that $F_n$ can be solved in the following way. As \begin{equation} \begin{pmatrix}F_{n+1}\\F_n\end{pmatrix} =\begin{pmatrix}1 & 1\\ 1&0\end{pmatrix} \begin{pmatrix}F_n\\F_{n-1}\end{pmatrix},\tag{1} \end{equation} we have \begin{equation} \begin{pmatrix}F_{n+1}\\F_n\end{pmatrix} =\begin{pmatrix}1 & 1\\ 1&0\end{pmatrix}^n \begin{pmatrix}F_1\\F_0\end{pmatrix}.\tag{2} \end{equation} In a broad sense, the derivation of $(2)$ from $(1)$ is mathematical induction, but in normal context, I think this is seldom regarded as such. Now, if this is not considered as mathematical induction, we can solve $(2)$ directly and hence we may and verify your inequality simply by plugging in the solution for $F_n$. (Edit: Or better, as Qiaochu Yuan suggests, one may simply compute the determinant of the matrix $n$-th power in $(2)$.)

share|improve this answer
3  
Alternately, you can just compute the determinant of that matrix you're using. –  Qiaochu Yuan Dec 26 '12 at 10:53
    
Ha ha, of course! –  user1551 Dec 26 '12 at 11:07

As, $F_{n+2}=F_{n+1}+F_n,$ the Characteristic equation of the recurrence relation will be $t^2-t-1=0$

If $a,b$ are the roots of the equation, $a+b=1,ab=-1$ and $F_n=Aa^n+Bb^n$ where $A,B$ are arbitrary constants.

So, $$F_{n+1}F_{n-1}-(F_{n})^2=(Aa^{n+1}+Bb^{n+1})(Aa^{n-1}+Bb^{n-1})-(Aa^n+Bb^n)^2$$ $$=AB\{a^{n+1}b^{n-1}+b^{n+1}a^{n-1}-2(ab)^n\}$$ $$=AB(ab)^n\{\frac{a^2+b^2}{ab}-2\}$$ $$=-5AB(-1)^n$$ as $\frac{a^2+b^2}{ab}-2=\frac{(a+b)^2}{ab}-4=-1-4=-5$

Now, $0=F_0=Aa^0+Bb^0\implies B=-A$

and $1=F_1=Aa+Bb=A(a-b)\implies A=\frac1{a-b}$

So, $AB=-A^2=\frac{-1}{(a-b)^2}=\frac{-1}{(a+b)^2-4ab}=-\frac15$

share|improve this answer
    
thanks lab, great –  doniyor Dec 26 '12 at 11:51
    
@doniyor, welcome –  lab bhattacharjee Dec 26 '12 at 12:33

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.