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!
Answer
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?
No comments:
Post a Comment