Wednesday, 15 May 2013

Generating function for kind of sum of Fibonacci numbers



Let's have a sequence

an=ni=0FiFni

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=bn1+bn2


I got that generating function for fib numbers is x1xx2
So, B(x)=x1xx2



and next an=ni=0bibni

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

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find limh0sin(ha)h without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...