Identity about Fibonacci numbers

109 Views Asked by At

If I note $(F_N)_N = \{0,1,1,2,3,5,...\}$ the Fibonacci sequence, I have proved the identity $$ \forall N \geqslant 0,\,F_{N}^2 = F_{N} + 2\,\sum_{k=0}^{N-3} F_{k+1}\,F_{k+2}\,F_{N-k-2}. $$

This relation can be obtained by induction and by using the equality $$F_{n+2}^2 =(F_{n+1}+F_n)^2=F^2_{n+1}+F^2_n+2F_{n+1}F_n.$$

Indeed we have

\begin{eqnarray*} F_{n+2}^2 &=& F^2_{n+1}+F^2_n+2F_{n+1}F_n \\ \\ &=& F_{n+1} + 2\,\sum_{k=0}^{n-2} F_{k+1}\,F_{k+2}\,F_{n-k-1} + F_{n} + 2\,\sum_{k=0}^{n-3} F_{k+1}\,F_{k+2}\,F_{n-k-2} + 2\,F_{n+1}F_n \\ \\ &=& F_{n+2} + 2\,\sum_{k=0}^{n-3} F_{k+1}\,F_{k+2}\,F_{n-k} + 2\,F_{n-1}F_n + 2\,F_{n+1}F_n \\ \\ &=& F_{n+2} + 2\,\sum_{k=0}^{n-1} F_{k+1}\,F_{k+2}\,F_{n-k}. \end{eqnarray*}

Question : I would like to know if anyone had ever seen a similar equality please. Thank you in advance.

1

There are 1 best solutions below

4
On

Define, for $n\ge3$, $\displaystyle S_n:=\sum_{k=0}^{n-3}F_{k+1}F_{k+2}F_{n-k-2}$. Then, the focus of your identity, $S_n=\frac{F_n^2-F_n}{2}$, is really on $S_n$ since the other terms are simpler.

Searching for the first few values of $S_n$ in the OEIS gives gives us sequence A191797, i.e. $S_n=\binom{F_n}{2}=\frac{2F_n^2-F_{n+4}+3F_{n+1}}{4}=T_{F_{n}-1}=\frac{F_n(F_n-1)}{2}$, where $\binom{n}{k}$ is the binomial coefficient and $T_n$ is the $n$th triangular number. This shows half your identity.

This should give you more places to look to see if the identity has been previously published. I've not found any reference to the sum of products formula, so it may be original.


We may prove the identity as follows

$$\require{cancel} \begin{align} S_n-S_{n-1} &=\sum_{k=0}^{n-3}F_{k+1}F_{k+2}F_{n-k-2}-\sum_{k=0}^{n-4}F_{k+1}F_{k+2}F_{n-1-k-2} \\ &=F_{n-2}F_{n-1}F_1+F_{n-3}F_{n-2}F_{2}+\sum_{k=0}^{n-5}F_{k+1}F_{k+2}F_{n-k-2}\ldots \\&\quad\ldots-\left(F_{n-3}F_{n-2}F_{1}+\sum_{k=0}^{n-5}F_{k+1}F_{k+2}F_{n-k-3}\right) \\ &=F_{n-2}F_{n-1}+\cancel{F_{n-3}F_{n-2}-F_{n-3}F_{n-2}}+\sum_{k=0}^{n-5}\left(F_{k+1}F_{k+2}F_{n-k-2}-F_{k+1}F_{k+2}F_{n-k-3}\right) \\ &=F_{n-2}F_{n-1}+\sum_{k=0}^{n-5}F_{k+1}F_{k+2}\left[\underbrace{F_{n-k-2}}_{F_{n-k-3}+F_{n-k-4}}-F_{n-k-3}\right] \\ &=F_{n-2}F_{n-1}+\sum_{k=0}^{(n-2)-3}F_{k+1}F_{k+2}\left(F_{(n-2)-k-2}\right) \\ &=F_{n-2}F_{n-1}+S_{n-2} \end{align} $$

With $S_3=F_1F_2F_{3-0-2}=1$ and $S_4=F_1F_2F_{4-0-2}+F_2F_3F_{4-1-2}=3$, this recurrence relation gives us an alternate definition for $S_n$. Therefore, the aim is to inductively prove that, for $n\ge 3$, $S_n=\frac{F_n(F_n-1)}{2}$. For the two base cases, $S_3=1=\frac{F_3(F_3-1)}{2}$ and $S_4=3=\frac{F_4(F_4-1)}{2}$. Then, assuming $S_k=\frac{F_k(F_k-1)}{2}$ and $S_{k+1}=\frac{F_{k+1}(F_{k+1}-1)}{2}$, we have

$$\begin{align}S_{k+2} &=F_{k}F_{k+1}+S_{k}+S_{k+1} \\ &=F_{k}F_{k+1}+\frac{F_k(F_k-1)}{2}+\frac{F_{k+1}(F_{k+1}-1)}{2} \\ &=\frac12\left(2F_{k}F_{k+1}+{F_k^2-F_k}+{F_{k+1}^2-F_{k+1}}\right) \\ &=\frac12\left(2F_{k}F_{k+1}+\left[F_{k-1}F_{k+1}-(-1)^k\right]+\left[F_{k}F_{k+2}-(-1)^{k+1}\right]-F_{k+2}\right)\tag{*} \\ &=\frac{1}{2}\left(F_{k+1}\left(2F_{k}+F_{k-1}\right)+F_{k}F_{k+2}-F_{k+2}\right) \\ &=\frac{1}{2}\left(F_{k+1}\left(F_{k}+F_{k+1}\right)+F_{k}F_{k+2}-F_{k+2}\right) \\ &=\frac{1}{2}\left(F_{k+1}F_{k+2}+F_{k}F_{k+2}-F_{k+2}\right) \\ &=\frac{F_{k+2}(F_{k+2}-1)}{2} \end{align} $$

This completes the proof. $(*)$ uses Cassini's identity, $F_{n-1}F_{n+1}-F_n^2=(-1)^n$.