1
$\begingroup$

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?

  • 0
    Without induction?2012-12-26
  • 1
    Then you seem to have defined $F_n$ without recursion?2012-12-26
  • 0
    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?2012-12-26
  • 0
    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?2012-12-26
  • 0
    so, now i think that the task is just for refreshing older topics in the book. i.e. induction. otherwise seems to be hard2012-12-26
  • 0
    @doniyor: I am not familiar with your textbook, but if the TASKS -part is about material for reviewing, then you last guess is probably close to the mark. After all, many converging sequences are also defined recursively, and induction is the tool there, too.2012-12-26
  • 0
    @doniyor: You can get a combinatorial proof for this result.2012-12-26
  • 0
    @Mohan can you pls give me that proof?2012-12-26
  • 1
    Go to page no 8 of this book. You can see the proof. http://books.google.co.in/books?id=FXLGzXwbwIAC&printsec=frontcover&source=gbs_atb#v=onepage&q&f=false2012-12-26
  • 0
    wow, Mohan, great, exactly this statement.. can you pls write your comment as an answer so that i can check as answer2012-12-26

2 Answers 2

3

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

  • 3
    Alternately, you can just compute the determinant of that matrix you're using.2012-12-26
  • 0
    Ha ha, of course!2012-12-26
1

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$

  • 0
    @doniyor, welcome2012-12-26