# Help me understand generating functions?

Printable View

• September 16th 2010, 08:56 AM
chickeneaterguy
Help me understand generating functions?
I don't understand generating functions...can someone please shine some light on this topic?

I don't see how to get from one point to another....for example:

Find a closed form for the generating functions of each of these sequences:
Each of the following already have the solutions, I just don't understand how to get to them.
a)0,0,0,1,2,3,4,...

$x^3/(1-x)^2$

b)1,1,0,1,1,1,1,1,1,1,...

$(1/(1-x))-x^2$

c)2,-2,2,-2,2,-2,2,-2,...

$2/(1+x)$

d) $C(7,0),C(7,1), C(7,3), \ldots, C(7,7),0,0,0,0,0,\ldots$

$(1+x)^7$

e)2,4,8,16,32,64,128,256,...

$2/(1-2x)$

f) 0,1,0,0,1,0,0,1,0,0,1,...

$x/(1-x^3)$

g)0,0,0,1,1,1,1,1,1,...

$x^3/(1-x)$

h)0,2,2,2,2,2,2,0,0,0,0,0...

$2x(1-x^6)/(1-x)$
• September 16th 2010, 11:32 AM
awkward
Hi ChickenEater,

All these problems require some facility working with infinite series, or in some cases just finite series. For example, consider the first problem. The ordinary power series generating function is, by definition,

$f(x) = x^3 + 2 x^4 + 3 x^5 + 4 x^6 + \dots$

It looks like it would pay to factor out x^3:

$f(x) = x^3 (1 + 2x + 3 x^2 + 4 x^3 + \dots)$

I don't remember a closed form for
$1 + 2x + 3 x^2 + 4 x^3 + \dots$,

but it reminds me of
$\frac{1}{1-x} = 1 + x + x^2 + x^3 + x^4 + \dots$.

Differentiating,
$\frac{1}{(1-x)^2} = 1 + 2x + 3x^2 + 4x^3 + \dots$

So
$f(x) = \frac{x^3}{(1-x)^2}$

Other series likely to prove useful (so you should know them) are the Binomial Theorem and the infinite series for e^x.

If you have a textbook, it's likely to list a some useful infinite series. If not, you can probably find a math handbook with some series that might come in handy.

Hope this helps--
• September 16th 2010, 11:38 AM
chickeneaterguy
Thanks. Your post helped a lot. I have a list of useful infinite series. I just didn't know where they were pulling the x's from and such. It makes a lot more sense now though.

Thanks again!!