# What are the basic generating functions?

What are the basic generating functions?
(if there is one's).

And what is the generating function of:

$$1 + 2x^2 + 3x^4 + 4x^6 + \cdots$$

Thanks.

-
What do you mean by "basic"? – Qiaochu Yuan May 11 '12 at 16:39
that i can use without proving. – Rami May 11 '12 at 16:40
That depends on who you're proving things to. – Qiaochu Yuan May 11 '12 at 16:45
The generating function of your sequence can be obtained by observing that $\frac{1}{1-x}=1+x+x^2+x^3$, so by differentiating in $x$, then multiplying by $x$ and adding 1 will give you the generating function – Alex R. May 11 '12 at 16:48
Use generating function instead of generation function. – Did May 12 '12 at 7:34

I guess you are looking for a table of common generating functions? You can look for Z trasforms tables, e.g. see here, and change $z^{-1}$ to $x$ (and restrict to right sided sequences).

And what is the generation function of...

Actually what you write is already the generating function, you are looking for a compact form. Consider first $G_1(x)= 1x + 2x^2 + 3 x^3+...$ (sequence $s_1 = (0,1,2,3...)$ This is just $G_1(x)=\frac{x}{(1-x)^2}$ (can be obtained directly by algebraic manipulation -see Michael's answer- or looking at entry 6 in that table)

Then the sequence $s_2 = (1,2,3...)$ has $G_2(x)=1+2 x + 3 x^2 =\frac{G_1(x)}{x} = \frac{1}{(1-x)^2}$ (and this is the "Time shifting property": shifting the sequence $k$ positions to the right divides the transform by $x^k$).

Instead our sequence is $s_3 = (1,0,2,0,3...)$ with $G_3(x)= 1+2x^2+3x^4+...$ but then $G_3(x)=G_2(x^2)$ (and this is the upsampling property) and you're done.

-

The most basic generating function comes from the geometric series: $$1 + x + x^2 + x^3 + \cdots = \frac{1}{1-x}.$$

If you differentiate this term by term, you get a new generating function: $$1 + 2x + 3x^2 + \cdots = \frac{d}{dx} \frac{1}{1-x}.$$

You can also get reindexed generating functions by multiplying by powers of $x$. For example, multiplying both sides of the geometric series by $x^3$ gives $$x^3 + x^4 + x^5 + x^6 + \cdots = \frac{x^3}{1-x}.$$

You can also get new generating functions by substitution. For example, using $x \mapsto x^2$ in the geometric series gives $$1 + x^2 + x^4 + x^6 + \cdots= \frac{1}{1-x^2}.$$

If you use some of the three ideas above, you'll be able to figure out your problem.

There are lots more techniques for dealing with generating fuctions -- see if you can find some of them on your own, or consult generatingfunctionology to study the topic in depth.

-
+1, for giving relevant hints. – Did May 12 '12 at 7:33
Thanks that was very helpful. – Rami May 12 '12 at 19:45

Most basic types, that arise often, are variants of:

$$(1 - z)^{-n} = \sum_{k \ge 0} (-1)^k \binom{-n}{k} z^k = \sum_{k \ge 0} \binom{k + n - 1}{n - 1} z^k$$

-