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.

Consider the Fibonacci numbers $F(0) = 0; F(1)=1; F(n) = F(n-1) + F(n-2)$.

Prove by induction that for all $n>0$,

$$F(n-1)\cdot F(n+1)- F(n)^2 = (-1)^n$$

I assume $P(n)$ is true and try to show $P(n+1)$ is true, but I got stuck with the algebra. How do we reach $P(n+1)$ from $P(n)$? Also, strong induction may be used instead.

share|improve this question
add comment

3 Answers

up vote 6 down vote accepted

Here is a pretty alternative proof (though ultimately the same), suggested by the determinant-like form of the claim. Let

$$M_n = \left(\begin{array}{cc} F(n+1) & F(n)\\ F(n) & F(n-1)\end{array}\right),$$

and note that

$$M_1 = \left(\begin{array}{cc} 1 & 1\\ 1 & 0\end{array}\right),$$

and

$$M_{n+1} = \left(\begin{array}{cc} 1 & 1\\ 1 & 0\end{array}\right) M_n.$$

It follows by induction that

$$M_n = \left(\begin{array}{cc} 1 & 1\\ 1 & 0\end{array}\right)^n.$$

Taking determinants (and using $\det(A^n) = \det(A)^n$) now gives the result.

share|improve this answer
add comment

Assume $F(n-1)F(n+1)-F(n)^2=(-1)^n$.

It is important to know what success will look like, so: We want to prove that $F(n)F(n+2)-F(n+1)^2=(-1)^{n+1}$. Immediately, this suggests to me that we should use our induction hypothesis right away, so substituting for $(-1)^n$ on the right we have that success will look like:

$F(n)F(n+2)-F(n+1)^2=F(n)^2-F(n-1)F(n+1)$

Note that we have not shown that this is true yet, this is the goal. Use the definitions of $F$ to get there: $F(n+2)=F(n+1)+F(n)$ and $F(n+1)=F(n)+F(n-1)$. Substituting this into $$F(n)F(n+2)-F(n+1)^2$$, we have $$F(n)F(n+2)-F(n+1)^2=\\F(n)[F(n+1)+F(n)]-F(n+1)[F(n)-F(n-1)]=\\F(n)^2-F(n+1)F(n-1)$$

Which is what we said success would look like! Now this is not really the proof, this is the scratch work for the proof. Take these steps and apply them backwards to write the actual proof.

Note that strong induction was not needed.

share|improve this answer
add comment

HINT: $F(n)F(n+2) - F(n+1)^2 = F(n)(F(n+1)+F(n)) - F(n+1)(F(n)+F(n-1))$.

share|improve this answer
add comment

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.