1
$\begingroup$

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!

$\endgroup$
2
  • 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$ Commented Mar 15, 2014 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$ Commented Mar 15, 2014 at 21:01

1 Answer 1

Reset to default
3
$\begingroup$

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?

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.