Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 1 down vote accepted

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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.