0
$\begingroup$

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.

  • 0
    How about writing $e^{\sum_k z^k/k^2}$ as $e^{z+z^2/4+z^3/9}$?2012-03-15

1 Answers 1

1

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