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!

  • 1
    $\begingroup$ 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)$$ $\endgroup$ – Steve Kass Mar 15 '14 at 20:26
  • $\begingroup$ 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}$ $\endgroup$ – 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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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