Fibonacci numbers and recurrence relations

120 Views Asked by At

Prove for $n\geq 1, F_n^2-F_{n+1}F_{n-1}=(-1)^n$.

I have verified for $n=1$, $F_1^2-F_{2}F_{0}=1-2(1)=-1=(-1)^1$.

Also, for $n=2$, $F_2^2-F_{3}F_{1}=4-3(1)=1=(-1)^2$.

To show for $k+1$, how would you incorporate the previous findings of $F_k$ into the proof for $F_{k+1}$?

2

There are 2 best solutions below

0
On

Proof by induction:

Induction base holds.

Induction step:

Assume that $$F_n^2-F_{n+1}F_{n-1}=(-1)^n.$$ Now we have $$F^2_{n+1}-F_{n+2}F_n=F^2_{n+1}-(F_{n+1}+F_n)F_n,$$ where we used identity $F_{n+2}=F_{n+1}+F_n$ for Fibonacci's numbers. $$F^2_{n+1}-F_{n+2}F_n=F^2_{n+1}-F_{n+1}F_n-F^2_n,$$ $$F^2_{n+1}-F_{n+2}F_n=F_{n+1}(F_{n+1}-F_n)-F^2_n,$$ $$F^2_{n+1}-F_{n+2}F_n=F_{n+1}F_{n-1}-F_n^2,$$ $$F^2_{n+1}-F_{n+2}F_n=(-1)(F_n^2-F_{n+1}F_{n-1}),$$ from where we get $$F^2_{n+1}-F_{n+2}F_n=(-1)(-1)^n=(-1)^{n+1}$$ by using induction assumption.

0
On

For the induction step, you can easily prove that $F_{n+1}^2-F_{n+2}F_n=F_{n+1}F_{n-1}-F_{n}^2$, for example using area considerations on the figure below:

Two adjacent squares, with sides $F_{n+1}$ and $F_n$

You can find other proofs of Cassini's identity here: Cassini's Identity