Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 $$


share|cite|improve this question
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
up vote 5 down vote accepted

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.

share|cite|improve this answer

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.

share|cite|improve this answer
+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 $$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.