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?

  • $\begingroup$ Does your version of $F_n$ have $F_0=F_1=1,$ or instead is it $F_0=0,F_1=1$? $\endgroup$ – coffeemath Oct 18 '16 at 4:42
  • 1
    $\begingroup$ Thanks for requesting the clarification. I've adjusted the question to make this clear. $\endgroup$ – Auslander Oct 18 '16 at 5:14
  • 1
    $\begingroup$ 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... $\endgroup$ – coffeemath Oct 18 '16 at 5:33
  • $\begingroup$ Yes. My thoughts too. The clean formula seems to suggest that there's a relatively clean method. $\endgroup$ – Auslander Oct 18 '16 at 5:37
  • $\begingroup$ You second formula cannot work if $a=0$, for instance for $G_n=F_n$... $\endgroup$ – 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.