2
$\begingroup$

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.

  • 1
    What do you mean by "basic"?2012-05-11
  • 0
    that i can use without proving.2012-05-11
  • 0
    That depends on who you're proving things to.2012-05-11
  • 0
    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 function2012-05-11
  • 1
    Use `generating function` instead of `generation function`.2012-05-12

3 Answers 3

0

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

8

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.

  • 0
    Thanks that was very helpful.2012-05-12
5

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.