Proof of a sequence with recursion

65 Views Asked by At

The problem asks to prove the following to be true.

$$F^2_{n+1} - F_{n+1} F_n - F_n^2 = (-1)^n$$

Anyway, I've tried looking at this or similar proofs for going on an hour now, pretty much the only thing I think I need to do is induction? So I would be setting n=k+1 but even just trying a base case (using 3) that leaves me with $$F^2_4 - F_4F_3 - F^2_3 = -1$$ which doesn't really get me anywhere. Do I need to somehow figure out a value to test for F? If so, any pointers/direction on how to pick a value of F or if I'm going at this the entirely wrong way will be very much appreciated, thanks in advance guys.

1

There are 1 best solutions below

5
On

For induction: Let $f_n$ the term of order $n$ in the Fibonacci sequence $(1,1,2,3,5,8,...)$.

First, if $k=1$, ok: $$f_2^2-f_2\cdot f_1-f_1^2=-1=(-1)^1. $$

Second, suppose that the equality is true for $n=k$, i.e., is true that $$f_{k+1}^2-f_{k+1}\cdot f_k-f_k^2=(-1)^k. $$ We need to show that is true for $n=k+1$, i.e., to show that $$f_{k+2}^2-f_{k+2}f_{k+1} -f_{k+1}^2=(-1)^{k+1}.$$ Indeed, as $f_{n+1}=f_{n}+f_{n-1}$ is true $\forall n\geq 1$, $$f_{k+2}^2-f_{k+2}f_{k+1} -f_{k+1}^2=(f_{k+1}+f_k)^2-(f_{k+1}+f_k)f_{k+1}-f_{k+1}^2 =$$ $$=f_{k+1}^2+2f_{k+1}f_k+f_k^2-f_{k+1}^2-f_{k+1}f_k-f_{k+1}^2 =$$ $$=-f_{k+1}^2+f_{k+1}f_k+f_k^2=-(f_{k+1}^2-f_{k+1}f_k+f_k^2)=-(-1)^k=(-1)^{k+1}. $$

Therefore, the result follows by induction, i.e., the equality is true.

Note: the key to the resolution was to transform the $ f_ {k +2} $ in terms of $ f_ {k +1} $ and $ f_k$.