# Sums of Squares of Fibonacci Numbers Using Difference Operators

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 $$F_0^2+F_1^2+\cdots+F_n^2=F_nF_{n+1}.$$ 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?

• Does your version of $F_n$ have $F_0=F_1=1,$ or instead is it $F_0=0,F_1=1$? – coffeemath Oct 18 '16 at 4:42
• Thanks for requesting the clarification. I've adjusted the question to make this clear. – Auslander Oct 18 '16 at 5:14
• It seems $G_n=aF_{n-2}+bF_{n-1}$ for $n \ge 3,$ which might make it possible to apply the known identity for sum of squares you cite to get this other sum for the more general sequence of $G_n$ -- So far the algebra looks forbidding to do that... – coffeemath Oct 18 '16 at 5:33
• Yes. My thoughts too. The clean formula seems to suggest that there's a relatively clean method. – Auslander Oct 18 '16 at 5:37
• You second formula cannot work if $a=0$, for instance for $G_n=F_n$... – lhf Oct 18 '16 at 11:09

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.

• Perfect. This self-generating answer is much cleaner than I anticipated. – Auslander Oct 18 '16 at 21:40