Sums of Squares of Fibonacci Numbers Using Difference Operators

Question

Consider the sequence of Fibonacci numbers $\{F_n\}_{n\geq0}$ where $F_0=0,F_1=1$ and $F_n=F_{n-1}+F_{n-2}$ for $n\geq2$. It is well-known and easily proved (by a variety of methods) that \begin{equation}F_0^2+F_1^2+\cdots+F_n^2=F_nF_{n+1}.\end{equation} Suppose we generalize the Fibonacci numbers so that we have a sequence $\{G_n\}_{n\geq0}$ such that $G_0=0,G_1=1$ and $G_{n}=aG_{n-1}+bG_{n-2}$ for $n\geq2$. We can show that $$b^nG_0^2+b^{n-1}G_1^2+\cdots+G_n^2=\frac{G_nG_{n+1}}{a}.$$ This formula is easy enough to prove by induction. But I was wondering how one might actually discover the formula? Is it obvious with the use of difference equations?

Answer 1

The following is a way to "construct" the identity.

We have for all $r \geqslant 0$ $$G_{r+1}G_r=G_r\left(aG_r+bG_{r-1}\right)=aG_r^2+bG_rG_{r-1}$$

which gives $$\tag 1\frac{G_{r+1}G_r}{a}=G_r^2+b \frac{G_rG_{r-1}}a$$

Now, starting with $r=n$ and then utilizing $(1)$ for one decremented value of $r$ at a time gives $$\begin{align} \frac{G_{n+1}G_n}{a}&=G_n^2+b \frac{G_nG_{n-1}}a\\ &=G_n^2+b\left(G_{n-1}^2+b\frac{G_{n-1}G_{n-2}}a\right)\\ &=G_n^2+bG_{n-1}^2+b^2\left(G_{n-2}^2+b\frac{G_{n-2}G_{n-3}}a\right)\\ \end{align}$$

If one is patient enough, this will eventually lead to $$\begin{align} \frac{G_{n+1}G_n}{a}&=G_n^2+bG_{n-1}^2+\dots+b^{n-1}\left(G_1^2+b\frac{G_{1}G_{0}}a\right)\\ &=\{G_0 = 0\}\\ &=G_n^2+bG_{n-1}^2+\dots+b^{n-1}G_1^2 \end{align}$$

Since $G_0 = 0$ we can of course add $b^nG_0^2$ leading to the desired result.