Let's have a sequence
an=n∑i=0FiFn−i
where Fn is n-th Fibonacci number.
I tried to solve it somehow, but i'm pretty stuck.
Defining Fibonacci numbers b0=0,b1=1,bn=bn−1+bn−2
I got that generating function for fib numbers is x1−x−x2
So, B(x)=x1−x−x2
and next an=n∑i=0bibn−i
then multiplying it by xn i get
A(x)=#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=(∞∑j=0Fjxj)(∞∑k=0Fkxk).
What is the coefficient of xn in this product?
No comments:
Post a Comment