Proving the Fibonacci identity $(−1)^{m−k}(F_{m+k+1}F_{m−k−1}−F_{m+k}F_{m−k}) =F_{k}^2+F_{k+1}^2$

Question

Prove that for two natural numbers $m$ and $k$, where $m>k$ the following identity holds:

$$(−1)^{m−k}(F_{m+k+1}F_{m−k−1}−F_{m+k}F_{m−k}) =F_{k}^2+F_{k+1}^2$$

Here the exercise comes with a hint: The constant is $F^2 _m$, try to substitute $k=0$ in.

Okay fair enough, let us try this, this will give us: $$ (−1)^{m}(F_{m+1}F_{m−1}−F_{m}F_{m}) =F_{0}^2+F_{1}^2$$ $$ (−1)^{m}(F_{m+1}F_{m−1}−F_{m}^2) =F_{0}^2+F_{1}^2=0^2+1^2=1$$

We can now use a identity by Cassini, namely that for $m>0=k$ we have: $$ (−1)^{m}(F_{m+1}F_{m−1}−F_{m}^2) =(-1)^m(-1)^m=(-1)^{2m}=1 \checkmark$$ Okay great, so our identity works whenever $k=0$, but I do not see how this helps with a generalisation.

---

Edit/idea: Did I just write down the base case for an approach via induction on $k$ perhaps?

Answer 1

I will give an outline of a proof, but leave the details to you. This is almost certainly not the method that you are expected to take, but it avoids the messy algebra of Binet's Formula.

One first proves (however they wish, perhaps by induction) that $$ F_{p+q} = F_{p-1}F_{q} + F_{p}F_{q+1} $$ for all integers $p,q$. Importantly, $p,q$ can be negative in the above formula. We also have that $$ F_{-n} = (-1)^{n+1}F_{n} $$ for all $n$. Then one gets $\textit{D'Ocagne's Identity}$: $$ F_{p-q} = (-1)^{q}\left(F_{p+1}F_{q-1} - F_{p-1}F_{q+1}\right) $$ as a simple corollary. Then from these one can prove that $$ F_{r}F_{a+b} = F_{a}F_{b+r} - (-1)^{r}F_{a-r}F_{b} $$ for all integers $a,b,r$. We can rewrite this as $$ F_{r}F_{a+b+r} = F_{a+r}F_{b+r} - (-1)^{r}F_{a}F_{b} $$ and hence if $a,b,c,d$ are integers such that $a+b=c+d$ then $$ F_{a+r}F_{b+r} - (-1)^{r}F_{a}F_{b} = F_{r}F_{a+b+r} = F_{r}F_{c+d+r} = F_{c+r}F_{d+r} - (-1)^{r}F_{c}F_{d} $$ and so for all such $a,b,c,d$ and any $r$ we have $$ F_{a}F_{b} - F_{c}F_{d} = (-1)^{r}\left(F_{a+r}F_{b+r} - F_{c+r}F_{d+r}\right) $$ From this we conclude that the LHS of your equation is simply $F_{2k+1}$, but then using the very first formula we wrote down we see that $$ F_{2k+1} = F_{(k+1) + k} = F_{k}^{2} + F_{k+1}^{2} $$

---

Just to add a few comments. In your question you stated some restrictions on the values that $m,k$ can take. It is clear from my proof that in fact the formula remains true for any integers $m,k$. I suspect that the exercise is stated as it is to avoid considering Fibonacci numbers with negative coefficients, but really this is a natural consideration. Since most of these formulae that hold for the positive index Fibonacci numbers hold for the negative index Fibonacci numbers too.

Answer 2

Using Binet's formula, we have:

$F_n = \frac{\phi^n - \psi^n}{\sqrt{5}}$ where $\phi = \frac{1+\sqrt{5}}{2}, \psi = \phi-1 = \frac{-1}{\phi}$

Then subbing it into your equation:

$(−1)^{m−k}(F_{m+k+1}F_{m−k−1}−F_{m+k}F_{m−k})$

$ = (−1)^{m−k}(\frac{\phi^{m+k+1} - \psi^{m+k+1}}{\sqrt{5}} \frac{\phi^{m-k-1} - \psi^{m-k-1}}{\sqrt{5}} - \frac{\phi^{m+k} - \psi^{m+k}}{\sqrt{5}} \frac{\phi^{m-k} - \psi^{m-k}}{\sqrt{5}})$

$ = (−1)^{m−k}(\frac{\phi^{2m} + \psi^{2m} - \phi^{m+k+1}\psi^{m-k-1} - \psi^{m+k+1}\phi^{m-k-1}}{5} - \frac{\phi^{2m} + \psi^{2m} - \phi^{m+k}\psi^{m-k} - \psi^{m+k}\phi^{m-k}}{5})$

$ = (−1)^{m−k}(\frac{ - \phi^{m+k+1}\psi^{m-k-1} - \psi^{m+k+1}\phi^{m-k-1}}{5} - \frac{ - \phi^{m+k}\psi^{m-k} - \psi^{m+k}\phi^{m-k}}{5})$

$ = (−1)^{m−k}(\phi\psi)^{m+k}(\frac{ - \phi\psi^{-2k-1} - \psi\phi^{-2k-1}}{5} + \frac{ \psi^{-2k} + \phi^{-2k}}{5})$

$ = (−1)^{m−k}(\phi\psi)^{m+k}(\phi-\psi)(\frac{\psi^{-2k-1} - \phi^{-2k-1}}{5})$

$ = (−1)^{m−k}(-1)^{m+k}(\frac{\phi-\psi}{\sqrt{5}})(\frac{\psi^{-2k-1} - \phi^{-2k-1}}{\sqrt{5}})$

$ = (−1)^{2m}(F_1)(F_{-2k-1})$

Now using the fact that $F_{-n} = (-1)^{n+1}F_n$,

$(F_1)(F_{-2k-1}) = (-1)^{-2k}(F_{2k+1})$

Using some tedious algebra, one can also show that $F_{2k+1} = F_{k}^2 + F_{k+1}^2$ and so,

$(F_{2k+1}) = F_{k}^2 + F_{k+1}^2$

Answer 3

Here is a proof based upon Binets formula \begin{align*} F_k=\frac{\varphi^k-\psi^k}{\varphi-\psi}\qquad k\geq 0\tag{1} \end{align*} where $\varphi=\frac{1}{2}\left(1+\sqrt{5}\right), \psi=\frac{1}{2}\left(1-\sqrt{5}\right)=-1/\varphi$.

We start with the right-hand side of OPs formula and obtain \begin{align*} F_k^2=\left(\frac{\varphi^k-\psi^k}{\varphi-\psi}\right)^2&=\frac{1}{(\varphi-\psi)^2}\left(\varphi^{2k}-2\left(\varphi\psi\right)^k+\psi^{2k}\right)\\ &=\frac{1}{(\varphi-\psi)^2}\left(\varphi^{2k}-2(-1)^k+\psi^{2k}\right)\tag{2}\\ \end{align*} Putting $k\to k+1$ in (2) we get \begin{align*} \color{blue}{F_k^2+F_{k+1}^2}&=\frac{1}{(\varphi-\psi)^2}\left(\varphi^{2k}-2(-1)^k+\psi^{2k}\right)\\ &\qquad+\frac{1}{(\varphi-\psi)^2}\left(\varphi^{2k+2}-2(-1)^k+\psi^{2k+2}\right)\\ &\,\,\color{blue}{=\frac{1}{(\varphi-\psi)^2}\left(\varphi^{2k}\left(1+\varphi^2\right)+\psi^{2k}\left(1+\psi^2\right)\right)}\tag{3} \end{align*}

And now the left-hand side.

We obtain \begin{align*} F_{m+k}F_{m-k}&=\frac{1}{\left(\varphi-\psi\right)^2}\left(\varphi^{m+k}-\psi^{m+k}\right)\left(\varphi^{m-k}-\psi^{m-k}\right)\\ &=\frac{1}{\left(\varphi-\psi\right)^2}\left(\varphi^{2m}-\varphi^{m+k}\psi^{m+k}-\varphi^{m-k}\psi^{m+k}+\psi^{2m}\right)\\ &=\frac{1}{\left(\varphi-\psi\right)^2}\left(\varphi^{2m}-\left(\varphi\psi\right)^{m-k}\left(\varphi^{2k}+\psi^{2k}\right)+\psi^{2m}\right)\\ &=\frac{1}{\left(\varphi-\psi\right)^2}\left(\varphi^{2m}+\psi^{2m}-(-1)^{m-k}\left(\varphi^{2k}+\psi^{2k}\right)\right)\tag{4} \end{align*} Replacing $k$ with $k+1$ in (4) we get \begin{align*} F_{m+k+1}F_{m-k-1}&=\frac{1}{\left(\varphi-\psi\right)^2}\left(\varphi^{2m}+\psi^{2m}+(-1)^{m-k}\left(\varphi^{2k+2}+\psi^{2k+2}\right)\right)\tag{5} \end{align*}

The left-hand side of OPs formula can now be rewritten using (4) and (5) as \begin{align*} \color{blue}{(-1)^{m-k}}&\color{blue}{\left(F_{m+k+1}F_{m-k-1}-F_{m+k}F_{m-k}\right)}\\ &=\frac{(-1)^{m-k}}{\left(\varphi-\psi\right)^2}\left(\varphi^{2m}+\psi^{2m}+(-1)^{m-k}\left(\varphi^{2k+2}+\psi^{2k+2}\right)\right)\\ &\qquad-\frac{(-1)^{m-k}}{\left(\varphi-\psi\right)^2}\left(\varphi^{2m}+\psi^{2m}-(-1)^{m-k}\left(\varphi^{2k}+\psi^{2k}\right)\right)\\ &\,\,\color{blue}{=\frac{1}{(\varphi-\psi)^2}\left(\varphi^{2k}\left(1+\varphi^2\right)+\psi^{2k}\left(1+\psi^2\right)\right)}\tag{6} \end{align*} A comparison of (3) and (6) shows OPs identity is valid.

Answer 4

I found another approach that is also very satisfying. We will use the fact that we can write the Fibonacci $Q$-matrix: $$Q^{m+k} Q^{k-m}=Q^k Q^k $$ $$\begin{pmatrix} F_{m+k+1} & F_{m+k} \\ F_{m+k} & F_{m+k-1} \end{pmatrix} \begin{pmatrix} F_{k-m+1} & F_{k-m} \\ F_{k-m} & F_{k-m-1} \end{pmatrix} = \begin{pmatrix} F_{k+1} & F_{k} \\ F_{k} & F_{k-1} \end{pmatrix} \begin{pmatrix} F_{k+1} & F_{k} \\ F_{k} & F_{k-1} \end{pmatrix} $$ We now compute the matrix product but are only interested in the first entry: $$\begin{pmatrix} F_{m+k+1}F_{k-m+1}+F_{m+k}F_{k-m} & \dots \\ \dots & \dots \end{pmatrix} = \begin{pmatrix} F^2_k+ F^2_{k+1} & \dots \\ \dots & \dots \end{pmatrix} $$ This gives us the following equality: $$ F_{m+k+1}F_{-(m-k-1)}+F_{m+k}F_{-(m-k)} = F^2_k+ F^2_{k+1} $$ Which is almost what we desire. Notice that as $m>k$, we actually know that $F_{m-k}$ and $F_{k-m-1}$ have negative indices, we will use the extension of the Fibonacci sequence to negative integers and the corresponding identity: $F_{-n}= (-1)^{n+1} F_n $, After applying this to our equality, we get: $$ F_{m+k+1}\cdot (-1)^{m-k-1+1} F_{m-k-1}+F_{m+k}\cdot (-1)^{m-k+1}F_{m-k} = F^2_k+ F^2_{k+1} $$ Now we simplify this to: $$ (-1)^{m-k} (F_{m+k+1} F_{m-k-1})- (-1)^{m-k}(F_{m+k} F_{m-k}) = F^2_k+ F^2_{k+1} $$ $$ (-1)^{m-k} (F_{m+k+1} F_{m-k-1}-F_{m+k} F_{m-k}) = F^2_k+ F^2_{k+1} $$ As desired $\square$.