How to prove this Fibonacci sequence statement: $F^2_{n+1} - F^2_{n-1} = F_{2n}$

Question

So the statement is:

Prove: $$F^2_{n+1} - F^2_{n-1} = F_{2n}$$

How could this be proven with induction?

What about without induction?

For induction I got here: (already tested $n=1$, and assumed $n=k$ held true)

$$F^2_{k+2} - F^2_{k} = F_{2k + 2}$$ $$(F_{k+1} + F_{k})^2 - (F_{k-1} + F_{k-2})^2 = F_{2k+1} + F_{2k}$$ Then you get some cancelation based off the $n=k$ case $$2F_{k+1}F_k + F_k^2 - 2F_{k-1}F_{k-2} - F_{k-2}^2 = F_{2k+1}$$

This is where I am stuck for the induction proof.

I have no idea where to begin with the non-induction proof.

Answer 1

Consider this matrix: $$A=\begin{bmatrix}1&1\\1&0\end{bmatrix}.$$ Matrix $A$ is such that $$A^n=\begin{bmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{bmatrix}.$$ Compute both $(A^n)^2$ and $A^{(2n)}$ (they are equal) and compare them entrywise: $$\begin{align}(A^n)^2&= \begin{bmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{bmatrix} \cdot\begin{bmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{bmatrix} \\ &=\begin{bmatrix}F^2_{n+1}+F^2_n &F_{n+1}F_{n}+F_{n}F_{n-1}\\ F_{n}F_{n+1}+F_{n-1}F_n &F^2_n+F^2_{n-1}\end{bmatrix} \\ &\equiv \begin{bmatrix}F_{2n+1}&F_{2n}\\F_{2n}&F_{2n-1}\end{bmatrix}=A^{(2n)}.\end{align}$$ So $$\begin{align}F_{2n}&=F_{n+1}F_n+F_{n-1}F_n=(F_{n+1}+F_{n-1})F_n=(F_{n+1}+F_{n-1})(F_{n+1}-F_{n-1})\\&=F^2_{n+1}-F^2_{n-1}.\end{align}$$

Answer 2

To prove it without induction, you can use the general formula for Fibonacci numbers:

$$F_n=\frac{ \phi_+^n - \phi_-^n}{\sqrt 5}$$

Where $\phi_\pm=\frac{1\pm\sqrt{5}}{2}$.

Answer 3

A direct proof:

$$F_{k+1}^2-F_{k-1}^2=(F_{k+1}-F_{k-1})(F_{k+1}+F_{k-1})=F_k(F_{k+1}+F_{k-1})=F_kF_{k+1}+F_{k-1}F_k\tag1$$

Summing both sides of (1) over $k$ and using this theorem, we arrive at our required result.

Answer 4

An alternative method other than induction:

Just by comparison of Fibonacci and Lucas numbers, you can easily find following two identities for all $n\ge 1$: $$L_n=F_{n-1}+F_{n+1}$$ and $$F_{2n}=F_{n}L_{n}$$ The product of these two equations leads to: $$F_{2n}L_n=F_{n}L_{n}\left(F_{n-1}+F_{n+1}\right)$$ Since $L_{n}\ne 0$ when $n\ge 0$, we can cancel $L_{n}$ from both side leading to: $$F_{2n}=F_{n}\left(F_{n-1}+F_{n+1}\right)$$ Now, by substituting $F_{n}=F_{n+1}-F_{n-1}$, we get: $$F_{2n}=\left(F_{n+1}-F_{n-1}\right)\left(F_{n+1}+F_{n-1}\right)=F_{n+1}^2-F_{n-1}^2$$ Done.