I'm a little confused on how convolution of formal series works mostly the indexing. This is the problem I'm working on.

Let $n$ and $k$ be fixed. Calculate $$\sum_{i=0}^{n}(-1)^{i}\binom{n}{i}i^{k}$$

My idea was to use generating functions I got

$$A(x)=\sum_{n\geq 0}\left(\sum_{i=0}^{n}(-1)^{i}\binom{n}{i}i^{k}\right)x^{n}$$ This looks like the convolution of two series, $(-1)^{i}i^{k}$ and $\binom{n}{i}$.

But I'm confused on the indexing. Would

$A(x)=B(x)C(x)$ where $B(x)=\sum_{n\geq0}\binom{n}{n-i}x^{n}$ and $C(x)=\sum_{n\geq0}(-1)^{n}n^{k}$? I think $B(x)$ is incorrect but what should be the index for $B(x)$?



Permit me to re-write this as $$(-1)^n \sum_{k=0}^n {n\choose k} (-1)^{n-k} k^m$$ because I use $i$ in complex variable calculations. Then we see immediately that $$A(z) = \sum_{n\ge 0} (-1)^n \frac{z^n}{n!} = \exp(-z).$$ Furthermore $$B(z) = \sum_{n\ge 0} n^m \frac{z^n}{n!} = z \exp(z) \sum_{q=1}^m {m \brace q} z^{q-1},$$ which may be verified by induction. Here we have used the Stirling numbers of the second kind.

It follows that $$A(z) B(z) = z \sum_{q=1}^m {m \brace q} z^{q-1}.$$ Therefore the sum is $$(-1)^n n! [z^n] A(z) B(z) = (-1)^n n! [z^{n-1}] \sum_{q=1}^m {m \brace q} z^{q-1} = (-1)^n n! {m \brace n}.$$

Addendum. The induction proof of the formula for $B(z)$ goes like this. Suppose $$B_m(z) = \exp(z) \sum_{q=1}^m {m \brace q} z^q.$$ Then $$B_{m+1}(z) = z \frac{d}{dz} B_m(z),$$ which gives $$B_{m+1}(z) = \exp(z) \sum_{q=1}^m {m \brace q} z^{q+1} + \exp(z) \sum_{q=1}^m {m \brace q} q z^q\\ = \exp(z)\left({m \brace m} z^{m+1} + \sum_{q=1}^m \left(q {m \brace q} + {m \brace q-1}\right)z^q \right) \\= \exp(z) \sum_{q=1}^{m+1} {m+1 \brace q} z^q$$ by the defining recurrence of the Stirling numbers of the second kind.

There is another calculation of this type at this MSE link -- I and at this MSE link -- II.


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.