# Prove $F_{n+1}F_{n-1}-(F_{n})^2=(-1)^n$ without induction

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?

-
Without induction? – Nameless Dec 26 '12 at 10:13
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
Go to page no 8 of this book. You can see the proof. books.google.co.in/… – Mohan Dec 26 '12 at 10:37

I think this depends on what is meant by "mathematical induction". Recall that $F_n$ can be solved in the following way. As $$\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}$$ we have $$\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}$$ 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)$.)

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

-
thanks lab, great – doniyor Dec 26 '12 at 11:51
@doniyor, welcome – lab bhattacharjee Dec 26 '12 at 12:33