2
$\begingroup$

For example in my textbook it says that the sequence for the generating function

$f(x) = (2x-3)^3$

is

$-27,54,-36,8,0,0,0,\dots$

I can see that plugging $0$ into the function gives me $-27$, but this doesn't hold true for $1$ and $54$. How do I get this sequence or the correct sequence for another generating function like

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

  • 2
    To compute the term $a_{n}$ in the sequence generated by an ordinary generating function, take the $n$-th derivative of the function at $x=0$ and divide by $n!$.2012-12-05

4 Answers 4

9

Let $f(x)=(2x-3)^3$; then after multiplying out we have $f(x)=-27+54x-36x^2+8x^3$, so if we write $f$ as a power series, $f(x)=\sum_{k\ge 0}a_kx^k\;,$ we must have $a_0=-27,a_1=54,a_2=-36,a_3=8$, and $a_k=0$ for $k\ge 4$.

For the second problem you have $f(x)=\frac{x^3}{1-x^2}\;.$ Deal with the denominator first. You should know the simple generating function that gives the sum of a geometric series:

$\frac1{1-x}=\sum_{k\ge 0}x^k\;.$ Replace $x$ by $x^2$, and you have

$\frac1{1-x^2}=\sum_{k\ge 0}\left(x^2\right)^k=\sum_{k\ge 0}x^{2k}\;.$

Finally, multiply by $x^3$:

$\frac{x^3}{1-x^2}=x^3\sum_{k\ge 0}x^{2k}=\sum_{k\ge 0}x^{2k+3}\;.$

Think of this now as $\sum_{k\ge 0}a_kx^k$; what are the coefficients $a_k$? It may help to write out a few terms of this sum:

$\frac{x^3}{1-x^2}=x^3+x^5+x^7+x^9+\ldots\;.$

Clearly $a_k=0$ when $k$ is even and when $k=1$, and $a_k=1$ when $k$ is an odd number greater than $1$. Thus, the associated sequence is $\langle 0,0,0,1,0,1,0,1,0,\dots\rangle\;.$

1

For the first example, these are the cofficents of the polynomial.

For the second example, $1/(1-x^2)=1+x^2+x^4+.....$, therefore $x^3/(1-x^2)=x^3+x^5+x^7+....$, thus the generating sequence is : 0,0,0,1,0,1,0,1,0,...

1

You are looking for a sequence $a_n$ with $f(x) = \sum_{k=0}^{\infty}a_nx^k$

Now $f(x) = (2x-3)^3 = -27x^0+54x^1-36x^2+8x^3+0x^4+0x^5+\dots$

so the generated sequence is $\{-27,54,-36,8,0,0,\dots\}$

1

In general, if a function can be represented as an infinite series $f(x)=\sum_{n=0}^\infty a_n x^n = a_0+a_1x+a_2x^2+\cdots,$ then it is said to be a generating function for the sequence $(a_n) = a_0, a_1, a_2, \dots$

For your first example, we can write $f(x)=(2x-3)^3 = -27 + 54x - 36x^2 + 8x^3+0.x^4+0.x^5+\cdots$ and so it generates the sequence $-27, 54, -36, 8, 0, 0, 0, \dots$