Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
1  
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 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 at 21:01

1 Answer 1

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|improve this answer

Your Answer

 
discard

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.