# how to find this generating function

this is the power series:

$$\sum_{i=0}^\infty n(n-1)^2 (n-2) z^n.$$

how can I find a generating function from it? I could use the third derivative but the $n-1$ is squared so I don't know what to do..

-
Is the summation index supposed to be an $n$? – joriki Nov 20 '11 at 23:26
Earth to Adam, come in please. 6 answers in 22 hours, and no word from you. Are the answers any good? Do you need more help? – Gerry Myerson Nov 21 '11 at 21:59

We can use $$\sum_{n=0}^\infty\binom{n}{k}z^n=\frac{z^k}{(1-z)^{k+1}}\tag{1}$$ which follows from differentiating $\sum\limits_{n=0}^\infty z^n=\frac{1}{1-z}$ repeatedly $k$ times and multiplying by $\dfrac{z^k}{k!}$, and $$n(n-1)^2 (n-2)=n(n-1)(n-2)(n-3)+2n(n-1)(n-2)\tag{2}$$ which is an example of the fact that any polynomial in $n$ can be written as a sum of $\binom{n}{k}$, we get \begin{align} f(z) &=\sum_{n=0}^\infty n(n-1)^2 (n-2) z^n\\ &=\sum_{n=0}^\infty n(n-1)(n-2)(n-3)z^n + 2n(n-1)(n-2)z^n\\ &=\sum_{n=0}^\infty 24\binom{n}{4}z^n + 12\binom{n}{3}z^n\\ &=\frac{24z^4}{(1-z)^5}+\frac{12z^3}{(1-z)^4}\\ &=\frac{12z^3(1+z)}{(1-z)^5}\tag{3} \end{align}

-

$$\begin{eqnarray} \sum_{n=0}^\infty n(n-1)^2 (n-2) z^n &=& z^3\sum_{n=0}^\infty n(n-1)^2 (n-2) z^{n-3} \\ &=& z^3\frac{\mathrm d^3}{\mathrm dz^3}\sum_{n=0}^\infty(n-1)z^n \\ &=& z^3\frac{\mathrm d^3}{\mathrm dz^3}z^2\sum_{n=0}^\infty(n-1)z^{n-2} \\ &=& z^3\frac{\mathrm d^3}{\mathrm dz^3}z^2\frac{\mathrm d}{\mathrm dz}\sum_{n=0}^\infty z^{n-1} \\ &=& z^3\frac{\mathrm d^3}{\mathrm dz^3}z^2\frac{\mathrm d}{\mathrm dz}\frac1{z(1-z)} \\ &=& \frac{12z^3(1+z)}{(1-z)^5} \end{eqnarray}$$

-
Shouldn't the $z^2$ in the 3rd/4th lines be $z$ to get a factor $n-1$ from the new $\frac{d}{dz}$? – Ross Millikan Nov 21 '11 at 0:22
@Ross: I don't think so. Our solutions are slightly different. You take two derivatives, then multiply by $z$ to get another factor $n-1$ right away; I first take three derivatives to get each factor once, and then I have to multiply by $z^2$ to get back to $n-1$, since the next "natural" factor would be $n-3$. – joriki Nov 21 '11 at 0:42
I believe there is an errant factor of $-1$ in there. – robjohn Nov 21 '11 at 0:48
@joriki: Yes I see. – Ross Millikan Nov 21 '11 at 0:50
Try $z=\frac{1}{2}$. The series is definitely positive, but the answer gives a negative. – robjohn Nov 21 '11 at 1:01

At wolframalpha.com enter

Sum n (n - 1)^2 (n - 2) z^n, n, 0, Infinity

-

If you expand the terms you have $\sum_{i=0}^\infty n*(n-1)^2*(n-2)*z^n=\sum_{i=0}^\infty (n^4-4n^3+4n^2-2n)z^n$ and you can deal with each term. Alternately $\sum_{i=0}^\infty n*(n-1)^2*(n-2)*z^n=\sum_{i=0}^\infty z^3\frac{d^2}{dz^2}z\frac {d^2}{dz^2}z^n$

-
The second alternative doesn't have the right powers of $z$. – joriki Nov 21 '11 at 0:03
@joriki: Hit send before finishing. Fixed now. Thanks – Ross Millikan Nov 21 '11 at 0:16

$$n*(n-1)^2 *(n-2) = n*(n-1)*(n-2)*(n-3+2)$$ $$= n*(n-1)*(n-2)*(n-3) + 2*n*(n-1)*(n-2)$$

Basically, the solution is z^3 multiplied by the fourth derivative plus two time the third derivative of $$\sum z^n = 1/(1-z)$$

-
You mean plus two times the third derivative? That's also not correct, since the powers of $z$ are reduced by taking the derivatives. – joriki Nov 20 '11 at 23:29
You're doubly right! I corrected it... Sorry again... – Fezvez Nov 22 '11 at 6:03

$$f(z)=\sum n(n-1)^2(n-2)z^n=12z^3+72z^4+240z^5+600z^6+1260z^7+\dots$$

$$(1-z)f(z)=12z^3+60z^4+168z^5+360z^6+660z^7+\dots$$

$$(1-z)^2f(z)=12z^3+48z^4+108z^5+192z^6+300z^7+\dots$$

$$(1-z)^3f(z)=12z^3+36z^4+60z^5+84z^6+108z^7+\dots$$

$$(1-z)^4f(z)=12z^3+24z^4+24z^5+24z^6+24z^7+\dots$$

From there, it should be easy.

EDIT: Note that this method will work for $\sum h(n)z^n$ for any polynomial $h$. If $h$ has degree $d$, then $(1-z)^{d+1}f(z)$ will be a polynomial, so you get your formula for $f(z)$. Note also that it requires no calculus, and is completely mechanical, needing no clever observations on ways to rewrite $h$.

-
If we take it just one step further, we get $$(1-z)^5f(z)=12z^3+12z^4+0z^5+0z^6+0z^7+\dots$$ which yields $$f(z)=\frac{12z^3+12z^4}{(1-z)^5}$$ – robjohn Nov 22 '11 at 6:39
@robjohn, that's why I wrote, "from there it should be easy." I figured it was only right to leave OP with some work to do. But OP has been conspicuously absent. – Gerry Myerson Nov 22 '11 at 6:45

In general, if $A(z) = \sum_{n \ge 0} a_n z^n$, you get: $$z \frac{\mathrm{d}}{\mathrm{d} z} A(z) = \sum_{n \ge 0} n a_n z^n$$ So, using $\mathrm{D}$ for "derivative," and $p(n)$ a polynomial: $$\sum_{n \ge 0} p(n) a_n z^n = p(z \mathrm{D}) A(z)$$ This gives a general method to get sums as yours. Just take care, e.g. $(z \mathrm{D})^2 \ne z^2 \mathrm{D}^2$.

-