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}\;?$$

$\endgroup$
  • 2
    $\begingroup$ 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!$. $\endgroup$ – mjqxxxx Dec 5 '12 at 0:26
8
$\begingroup$

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\;.$$

$\endgroup$
1
$\begingroup$

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,...

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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