# Coefficient of $z^{n-1}$ term in a generating function

This is a problem from Concrete Mathematics (Eq. 9.57 and 9.58 in 1995 edition).

$G(z) = \sum_{k}g_k z^k = e^{\sum_{k} \frac{z^k}{k^2}}$ is a generating function of sequence $g_k$. By taking the derivative wrt $z$ we get $G'(z) = \sum_{k} \frac{z^{k-1}}{k} G(z)$ and at the same time of course $G'(z) = \sum_k k g_k z^{k-1}$. Coefficient at $z^{n-1}$ term would be obviously $n g_n$. What I can't sort out why coefficient on the other side of the equation is $\sum_{k=1}^{n-1} \frac{g_k}{n-k}$. I were trying to derive some convolution by expanding the exponential function, but couldn't quite make it.

Please don't solve it, some hints will do.

-
How about writing $e^{\sum_k z^k/k^2}$ as $e^{z+z^2/4+z^3/9}$? – FiniteA Mar 15 '12 at 6:34

It's hard to give a hint without providing the answer, since you've already given the right hint yourself: It's a convolution. In $G'(z) = \sum_{k} \frac{z^{k-1}}{k} G(z)$, substitute $G(z) = \sum_{k}g_k z^k$, and then collect terms with the same power of $z$, keeping in mind that you want the $z^{n-1}$ term and that the sum in $G'(z) = \sum_{k} \frac{z^{k-1}}{k} G(z)$ starts at $k=1$.