Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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
up vote 3 down vote accepted

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?

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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