# Generating function for kind of sum of Fibonacci numbers

Let's have a sequence $$a_n = \sum_{i=0}^n F_iF_{n-i}$$ where $F_n$ is n-th Fibonacci number.

I tried to solve it somehow, but i'm pretty stuck. Defining Fibonacci numbers $$b_0=0, b_1=1, b_n=b_{n-1}+b_{n-2}$$ I got that generating function for fib numbers is $\frac{x}{1-x-x^2}$ So, $B(x)=\frac{x}{1-x-x^2}$

and next $$a_n = \sum_{i=0}^n b_ib_{n-i}$$ then multiplying it by $x^n$ i get $A(x) = \text{#here im stuck#}$ What would be the right side of equation? I'm pretty confused about it.

I will greatly appreciate some help, thanks in advance!

• Hint: What is the coefficient of $x^3$ in this product? $$(b_0+b_1x+b_2x^2+b_3x^3+b_4x^4+\cdots)(b_0+b_1x+b_2x^2+b_3x^3+b_4x^4+\cdots)$$ – Steve Kass Mar 15 '14 at 20:26
• This isn't a hint, but I thought it was interesting. If you take the result of this calculation, you can use partial fractions to evaluate the original sum in terms of the Fibonacci and Lucas numbers: $\sum_{i=0}^n F_i F_{n-i} = \frac{nL_n - F_n}{5}$ – Slade Mar 15 '14 at 21:01

This is that sort of thing that is probably easier to recognize when you've done it the other way around first. I.e. consider expanding the product $$B(x)^2 = \left(\sum_{j=0}^\infty F_j x^j\right) \left( \sum_{k=0}^\infty F_k x^k \right).$$ What is the coefficient of $x^n$ in this product?