4
$\begingroup$

I'm reading and enjoying "generatingfunctionology". What a great fun book!

But, I'm having some difficulty with the exercises. For example, take the series $a_n = n^2$ I'd like to find the Generating function, $S(x)=\sum\limits_{n=0}^N a_n x^n = 0+1x^1+ 4x^2 + 8x^3 + \cdots$ using the method in the book. So, I find a recursive formula for $a_{n+1}=a_n + 2n +1$ then multiply on both sides by $x^n$ and sum over n. Next I replace every instance of $S(x)$ I can find with "$S(x)$" and then solve for $S(x)$.

$\sum_{n=0}^{\infty} a_{n+1}x^n = \sum_{n=0}^{\infty}a_n x^n + \sum_{n=0}^{\infty} 2n x^n + \sum_{n=0}^{\infty} x^n$

But, this is just:

$\frac{S(x)- a_0}{x} = S(x) + 2 \frac{x}{(1-x)^2} + \frac{1}{1-x}$

But, when I solve for S(x) I get $S(x) = \dfrac{x(1+x)}{(1-x)^3}$, but the solution in the book is $(xD)^2\left(\dfrac{1}{1-x}\right)$. And $(xD)^2\left(\dfrac{1}{1-x}\right) = -\dfrac{x(1+x)}{(1-x)^3}$.

Two questions:

  • Why do I have the wrong sign?
  • How would I know that my answer could be written in terms of differential operators like that? Maybe there is a better way of solving that would give me differential operators right away?

Thanks!

  • 0
    Are you sure you computed $(xD)^2 (1-x)^{-1}$ correctly?2011-12-04

1 Answers 1

5

Start with the known generating function $\frac1{1-x}=\sum_k x^k$ and apply the $xD$ operator twice. The first time you get

$\frac{x}{(1-x)^2}=xD\left(\frac1{1-x}\right)=xD\left(\sum_kx^k\right)=x\sum_k kx^{k-1}=\sum_k kx^k,$

and the second time you get $(xD)^2\left(\frac1{1-x}\right)=xD\left(\sum_k kx^k\right)=x\sum_k k^2x^{k-1}=\sum_k k^2x^k,$ which is exactly what you want. Spotting this is a matter of recognizing that two applications of $xD$ to the original power series will give the series with the desired coefficients.

The answer to your other question is simply that you differentiated incorrectly: $\begin{align*} xD\left(\frac{x}{(1-x)^2}\right)&=x\cdot\frac{(1-x)^2+2x(1-x)}{(1-x)^4}\\ &=\frac{x(1-x+2x)}{(1-x)^3}\\ &=\frac{x(1+x)}{(1-x)^3}. \end{align*}$