I'm looking for a short and precise proof of the following identity;

$$\left(\sum_{k=0}^\infty \frac{C_k}{k!}x^k\right)^n=\sum_{k=0}^\infty\left[ \sum_{(j_1+...+j_n=k)}\binom{k}{j_1,...,j_n}\frac{C_{j_1}\cdot...\cdot C_{j_n}}{k!}\right]x^k$$

I've got the idea through brute force of smaller convolutions when $n=2,3,4$ and I've used Mathematica to show that the identity holds for the previous cases. But I was hoping for something compact.


The coefficient of $x^k$ in $$\left(\sum_{k\ge 0}\frac{C_k}{k!}x^k\right)^n$$ is the sum of all possible products of the form


where the $j_i$ are non-negative integers whose sum is $k$. Thus, it’s

$$\begin{align*} \sum_{j_1+\ldots+j_n=k}\frac{C_{j_1}\cdot\ldots\cdot C_{j_n}}{j_1!\cdot\ldots\cdot j_n!}&=\sum_{j_1+\ldots+j_n=k}\left(\frac{k!}{j_1!\cdot\ldots\cdot j_n!}\cdot\frac{C_{j_1}\cdot\ldots\cdot C_{j_n}}{k!}\right)\\\\ &=\sum_{j_1+\ldots+j_n=k}\binom{k}{j_1,\ldots,j_n}\frac{C_{j_1}\cdot\ldots\cdot C_{j_n}}{k!}\;. \end{align*}$$

  • $\begingroup$ I appreciate the help here. I just have question. Outside of just expanding and observing, how do you know that the coefficient is the sum of all possible products of the form above? $\endgroup$ Nov 27 '14 at 2:47
  • 1
    $\begingroup$ @Eleven-Eleven: I don’t actually have to do the expansion to realize that $\left(\sum_{k\ge 0}\frac{C_k}{k!}x^k\right)^n$ is the sum of all possible terms of the form $\prod_{i=1}^n\left(\frac{C_{j_i}}{j_i!}x^{j_i}\right)$ with $j_i\in\Bbb N$, and from there it’s immediate. $\endgroup$ Nov 27 '14 at 2:57
  • $\begingroup$ @Eleven-Eleven: You’re welcome! $\endgroup$ Nov 27 '14 at 3:13
  • $\begingroup$ I just realized how simple that idea is...I foiled a couple of trinomials in my head, saw the multiplication and addition withing the coefficients. Thanks again. $\endgroup$ Nov 27 '14 at 3:15
  • 1
    $\begingroup$ @Eleven-Eleven: Glad to be of help! Getting that kind of insight is even better than just getting the question answered. $\endgroup$ Nov 27 '14 at 3:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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