# how to find generating function with nested sums

I'm trying to figure out the generating function for this power series.. I have a few ideas but can't get any result..

$$\sum_{n=2}^\infty \left(\sum_{k=1}^{n} ((n-k)(k-1)M_{k-1}) z^n\right)$$

$M(k)$ is my recursive function.. my problem is with the $(n-k)(k-1)$ part..

I was thinking that it can be extracted from the summation and it should become

$$n(n+1)(n+2)/6$$

but I'm still unable to solve this..

-
A generating function and a (formal) power series are the same thing, so it's not clear what you're asking. –  Dimitrije Kostic Nov 21 '11 at 5:37
Have you tried applying convolution backwards? –  Raphael Nov 21 '11 at 6:54
If you want to solve for $M_k$, you should give the original recursion in your question. –  Raphael Nov 21 '11 at 19:28

$$\sum_{n\geq2} \sum_{k=1}^{n}(n-k)(k-1)M_{k-1}z^n = \sum_{n\geq1} \sum_{k=1}^{n+1}(n+1-k)(k-1)M_{k-1}z^{n+1}$$ Interchanging order of sum: $$[1 \leq n < \infty][1 \leq k \leq n+1] =[1 \leq k \leq n+1 < \infty]$$ $$= [1 \leq k < \infty][k \leq n+1 < \infty]$$ Hence, $$= \sum_{k\geq 1}(k-1)M_{k-1}\sum_{n+1\geq k}(n+1-k)z^{n+1-k}z^k$$ $$= \sum_{k\geq 1}(k-1)M_{k-1}\sum_{n\geq k}(n-k)z^{n-k}z^k$$ $$=\sum_{k\geq 1}(k-1)M_{k-1}z^k \;z\sum_{n\geq k}(n-k)z^{n-k-1}$$ $$=\sum_{k\geq 1}(k-1)M_{k-1}z^{k+1} \;\frac{d}{dz}\sum_{n\geq k}z^{n-k}$$ $$=\sum_{k\geq 1}(k-1)M_{k-1}z^{k+1} \;\frac{1}{(1-z)^2}$$ $$=\frac{z^3}{(1-z)^2}\sum_{k\geq 1}(k-1)M_{k-1} z^{k-2}$$ $$=\frac{z^3}{(1-z)^2}\sum_{k\geq 1}(k-1)M_{k-1} z^{k-2}$$ $$=\frac{z^3}{(1-z)^2}\frac{d}{dz}\sum_{k\geq 1}M_{k-1} z^{k-1}$$

-

Observe the inner product is a discrete convolution, suggesting this is a product of two generating functions. Reindex $n$ by $1$ and obtain:

$$\sum_{n=2}^\infty\left(\sum_{k=1}^n(n-k)(k-1)M_{k-1}\right)z^n=\sum_{n=1}^\infty\left(\sum_{a+b=n}a\cdot(bM_b)\right)z^{n+1}$$

$$=z\left(\sum_{a=1}^\infty az^a\right)\left(\sum_{b=1}^\infty bM_bz^b\right)=z\cdot\frac{z}{(1-z)^2}\cdot\left(z\frac{d}{dz}\sum_{b=1}^\infty M_bz^b\right).$$

Now, what is it exactly that you want to accomplish here? You say $M_k$ is a recursive function but you don't tell us what the recursion it satisfies is and you likewise refer to some "it" being a given polynomial in $n$ but what is the "it" that you refer to - is it the $M_k$ or the inner sum involving $M_k$?

Also, if you meant $z^k$ instead of $z^n$ in your first equation...

-