Generating function for squared fibonacci numbers

Question

We know that generating function for fibonacci numbers is $$B(x)=\frac{x}{1-x-x^2}$$

How can we calculate $B(x)^2$? I thought that, if we have $B(x)=F_n*x^n$ then $$B(x)*B(x) = \sum_{n=0}^\infty (\sum_{i=0}^n F_iF_{n-i})x^n$$

And $$B(x)^2 = (\frac{x}{1-x-x^2})^2$$, but it's not true, because according to oeis, generating function for this is $$\frac{x(1-x)}{(1+x)(1-3x+x^2)}$$

I'd really appreciate some help on this

Answer 1

Use two consecutive Leonardo (da Pisa, called Fibonacci) recursion equations \begin{align} F_{n+2}&=F_{n+1}+F_{n}\\ F_{n-1}&=F_{n+1}-F_n \end{align} square them and add them \begin{align} F_{n+2}^2&=F_{n+1}^2+F_{n}^2+2F_{n+1}F_{n}\\ F_{n-1}^2&=F_{n+1}^2+F_n^2-2F_{n+1}F_n\\[0.3em]\hline F_{n+2}^2+F_{n-1}^2&=2F_{n+1}^2+2F_n^2 \end{align} Now find the generating function for this recursion formula.

Answer 2

Note that generating functions are not usually a good tool for studying the square of a sequence, since there is no general relationship between the generating function of $a_n$ and the generating function of $a_n^2$.

Here is an approach that I like:

Let $\tau$ and $\bar{\tau}$ be the positive and negative roots, respectively, of the equation $z^2-z-1=0$. In other words, we have $1-x-x^2 = (1-\tau x)(1-\bar{\tau} x)$. Then we can write the Fibonacci numbers as $$F_n = \frac{\tau^n-\bar{\tau}^n}{\tau-\bar{\tau}} =\frac{1}{\sqrt{5}} (\tau^n-\bar{\tau}^n)$$. We can convert this formula to and from the generating function form using partial fractions.

It's also useful to have another sequence handy, the Lucas sequence $L_n$, which has $L_0=2$, $L_1=1$, and satisfies the same recursion as $F_n$. It has generating function $A(x)=\frac{2-x}{1-x-x^2}$, and closed form $$L_n = \tau^n+\bar{\tau}^n $$

With this sequence in mind, we can do calculations involving Fibonacci numbers very quickly and mechanically (note that $\tau \bar{\tau}=-1$): $$F_n^2 = \frac{1}{5}(\tau^{2n} -2\tau^n \bar{\tau}^n+\bar{\tau}^{2n}) = \frac{1}{5}(\tau^{2n} + \bar{\tau}^{2n} -2(\tau \bar{\tau})^n) = \frac{L_{2n}-2(-1)^n}{5} $$

If we want to, we can get the generating function directly from this formula. The generating function for $(-1)^n$ is easily seen to be $\frac{1}{1+x}$. I already mentioned the generating function $A(x)$ for $L_n$, but to get the generating function for $L_{2n}$, we must calculate $\frac{1}{2} (A(\sqrt{x})+A(-\sqrt{x}))$. It follows that this is the generating function of $F_n^2$:

$$\frac{1}{10}(\frac{2-\sqrt{x}}{1-\sqrt{x}-x}+\frac{2+\sqrt{x}}{1+\sqrt{x}-x}-\frac{4}{1+x}) = \frac{x(1-x)}{(1+x)(1-3x+x^2)}$$