Coefficients of a generating function

134 Views Asked by At

I need a bit of help. I was solving the form of the coefficients of the generating function $\sum_{n}n^m r^n$.

Then I started building the indefinite sum $\sum n^m r^n \delta n$ through recursive summation by parts. I have the formula for recursive summation by parts

$$\sum f \Delta g=\sum_{k\ge 0}(-1)^k\ \Delta ^k f\ \frac{E^k}{\Delta^k}g$$

where $Ef(k)=f(k+1)$ is the shift operator, $\Delta$ is difference and $\Delta ^{-1}$ is indefinite sum.

I know that

$$f=n^m=\sum_{j=0}^{m}\left\{m\atop j\right\}n^\underline j \to \Delta f=\sum_{j=0}^{m}\left\{m\atop j\right\}jn^\underline {j-1} \to \Delta^k f=\sum_{j=0}^{m}\left\{m\atop j\right\}j^\underline{k} n^\underline {j-k}$$

$$\Delta g=r^n \to g=\frac{r^n}{r-1} \to \frac{E^k}{\Delta^k}g=\left( \frac{r}{r-1}\right)^{k} \frac{r^n}{r-1}$$

Then

$$\sum n^m r^n \delta n=\sum_{k\ge0}(-1)^k\ \left( \frac{r}{r-1}\right)^k \frac{r^n}{r-1} \sum_{j=0}^{m}\left\{m\atop j\right\}j^\underline{k} n^\underline {j-k}$$

And because a generating function is the series for $n\ge0$ and you can consider $|r|<1$ then delimiting the sum as $\sum_{n=0}^{\infty}$ I have

$$f(r)=\sum_{n=0}^{\infty} n^m r^n=\sum_{k\ge 0}(-1)^{k+1}\ \left( \frac{r}{r-1}\right)^k \frac{1}{r-1}\left\{m\atop k\right\}k!$$

But then when I try to find $[r^k]f(r)$ I encounter some wrong answer. The real answer must be $[r^k]f(r)\frac{(1-r)^{m+1}}{r}=\left\langle m\atop k\right\rangle$ i.e. the eulerian numbers.

I did some mistake somewhere but I cant see it. My intuition says that there is a mistake involving $n=0$ so I will try to take the coefficient for $\sum_{n\ge1}n^m r^n$ that after all is the same that from $n=0$.

P.S.: this is the $(e)$ part of problem $1$ from generatingfunctionology. I know there is a solution on the book but anyway Im interested in this approach.

1

There are 1 best solutions below

0
On BEST ANSWER

I finally solved the question. When I was trying to do it I was so tired so I had a lot of mistakes that I overlooked.

I have 2 big mistakes that I edited in the original question (mistake in red):

1) $(r-1)^k(-1)\color{red}{=}(1-r)^k\ $yeah, is terrible, I know

2) $\sum f \color{red}{\Delta} g=\sum_{k\ge 0}(-1)^k\ \Delta ^k f\ \frac{E^k}{\Delta^k}g\ $ I forget the first delta symbol :/

With these mistakes fixed then I have:

$$f(r)=\sum_{n=0}^{\infty} n^m r^n=\sum_{k\ge 0}(-1)^{k+1}\ \left( \frac{r}{r-1}\right)^k \frac{1}{r-1}\left\{m\atop k\right\}k!=\\ =\frac{(-1)^{m+1}r}{(r-1)^{m+1}}\sum_{k\ge 0}(-1)^{k-m}\ r^{k-1}(r-1)^{m-k}\left\{m\atop k\right\}k!$$

To simplify I will name $A=(-1)^{m+1}r/(r-1)^{m+1}$

$$f(r)=A\sum_{k\ge0}(-1)^{k-m}\ r^{k-1}\left\{m\atop k\right\}k!\left (\sum_{h=0}^{m-k}\binom{m-k}{h}r^h(-1)^{m-k-h} \right )$$

Then doing a bit of algebra and equating coefficients I finally have that

$$\boxed{[Ar^x]f(r)=\sum_{k=1}^{x+1}(-1)^{k-x-1}\binom{m-k}{m-x-1}\left\{m\atop k\right\}k!=\left\langle m\atop x\right\rangle}$$

Im happy, I can die in peace by now :)