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
Best Answer
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.