# Closed-form expression for $\sum_{k=0}^n\binom{n}kk^p$ for integers $n,\,p$

Is there a closed-form expression for the sum $\sum_{k=0}^n\binom{n}kk^p$ given positive integers $n,\,p$? Earlier I thought of this series but failed to figure out a closed-form expression in $n,\,p$ (other than the trivial case $p=0$).

$$p=0\colon\,\sum_{k=0}^n\binom{n}kk^0=2^n$$

I know that $\sum_{k=0}^n\binom{n}k=2^n$ and $\sum_{k=0}^nk^n=\frac{k^{n+1}-1}{k-1}$ but I am unsure of whether these would be of much use now.

Additionally, what about the similar series $\sum_{k=0}^n\binom{n}kk^n$ where $p=n$?

• Is it $k^p$ or $k^n$? – Mhenni Benghorbal Apr 8 '13 at 21:37
• @MhenniBenghorbal $k^p$, my mistake -- though that series looks very interesting as well! :-) – oldrinb Apr 8 '13 at 21:38

If you consider $p$ as fixed, then the below can be considered as closed form I suppose:

$$\sum_{k=0}^{n} \binom{n}{k} k^p = \sum_{k=1}^{p} s(p,k) n(n-1)\dots(n-k+1) 2^{n-k} \quad \quad (1)$$

where $s(k,p)$ is a stirling number of the second kind.

If you denote the operator of differentiating and multiplying by $x$ as $D_{x}$

Then we have that

$$(D_{x})^{n}f(x) = \sum_{k=1}^{n} s(n,k) f^{k}(x) x^{k}$$

where $s(n,k)$ is the stirling number of the second kind and $f^k(x)$ is the $k^{th}$ derivative of $f(x)$.

This can easily be proven using the identity $$s(n,k) = s(n-1,k-1) + k \cdot s(n-1,k)$$

To prove $(1)$ above, we apply $D_x$, $p$ times to $(1+x)^n$, and set $x=1$.

• Interesting approach. Am I right in concluding this is roughly the same argument as in Michael's solution above? – oldrinb Apr 8 '13 at 21:47
• @oldrinb: Yes, but it aims to give a formula in terms of well known numbers :-). The approach of differentiating and multiplying by $x$ is a pretty well known approach. For instance, see my answer here: math.stackexchange.com/questions/4317/… – Aryabhata Apr 8 '13 at 21:48
• thanks for that... I haven't been exposed to this before! – oldrinb Apr 8 '13 at 21:50
• In your formula, is it $s(p,k)$ or s(k,p)? – Mhenni Benghorbal Apr 8 '13 at 22:11
• @MhenniBenghorbal: $s(p,k)$, same as what you have. – Aryabhata Apr 8 '13 at 22:13

Let $$f(x)=(e^x+1)^n=\sum_{k=0}^n \binom{n}{k}e^{kx}.$$

Then $$\left(\frac{d}{dx}\right)^p f(x)=\sum_{k=0}^n\binom{n}{k}k^pe^{kx}.$$

Plug in $x=0$.

• Elegant and concise -- too good! Pretty neat. – oldrinb Apr 8 '13 at 21:55
• @oldrinb: I guess our definitions of closed form formula differ :-) Or do you see an easy way to compute the left side in this answer? – Aryabhata Apr 8 '13 at 22:01
• @Aryabhata true, I was just surprised by how concise this was. – oldrinb Apr 8 '13 at 22:02
• Of course, we could write it as an integral (Cauchy's formula), so +1 to this answer. – Aryabhata Apr 8 '13 at 22:03
• @Aryabhata: The closed form that you have will follow from this, use $e^x+1=e^x-1+2$. (+1) on your answer! – Sungjin Kim Apr 8 '13 at 22:08

We know that $(1+x)^n=\sum_{k=0}^n \binom{n}{k}x^k$.Differentiate this, to get $n(1+x)^{n-1}=\sum_{k=0}^n \binom{n}{k} k x^{k-1}$. Multiply by $x$ to get $nx(1+x)^{n-1}=\sum_{k=0}^n \binom{n}{k} k x^k$. Take $x=1$ to get the first sum, And repeat this process for sums involving higher powers of $k$.

• Brilliant! I would have never seen this. – oldrinb Apr 8 '13 at 21:48

Use the identity $k\dbinom{n}k=n\dbinom{n-1}{k-1}$: for $p=1$ you get

$$\sum_k\binom{n}kk=n\sum_k\binom{n-1}{k-1}=n\sum_k\binom{n-1}k=n2^{n-1}\;.$$

For $p=2$:

\begin{align*} \sum_k\binom{n}kk^2&=n\sum_k\binom{n-1}{k-1}k\\ &=n\sum_k\binom{n-1}k(k+1)\\ &=n\sum_k\binom{n-1}kk+n\sum_k\binom{n-1}k\\ &=n(n-1)\sum_k\binom{n-2}{k-1}+n2^{n-1}\\ &=n(n-1)\sum_k\binom{n-2}k+n2^{n-1}\\ &=n(n-1)2^{n-2}+n2^{n-1}\;. \end{align*}

If you carry out the same sort of computation with $p=3$, you get

$$\sum_k\binom{n}kk^3=n(n-1)(n-2)2^{n-3}+2n(n-1)2^{n-2}+n2^{n-1}\;,$$

which can be written with falling factorials as $$\sum_k\binom{n}kk^3=n^{\underline3}2^{n-3}+3n^{\underline2}2^{n-2}+n^{\underline1}2^{n-1}\;.$$

After a little more experimentation one may conjecture and prove by induction that

$$\sum_k\binom{n}kk^p=\sum_{k=1}^p{p\brace k}n^{\underline k}2^{n-k}\;,$$

where $p\brace k$ is the Stirling number of the second kind.

• This does make sense and it's an interesting approach. Thank you! – oldrinb Apr 8 '13 at 21:58
• @oldrinb: You’re welcome! – Brian M. Scott Apr 8 '13 at 21:58

A relate problem. Try this formula $$\sum_{k=0}^n\binom{n}kk^p= 2^n\sum_{k=0}^{p}\begin{Bmatrix} p\\k \end{Bmatrix} {n\choose k}2^{-k}k!,$$

where $p \in \mathbb{N}$ and $\begin{Bmatrix} p\\k \end{Bmatrix}$ is the Stirling numbers of the second kind. You can plug in $p=n$ in the above formula.

• You might be missing a $2^{-k}$ factor inside the $\sum$. – Aryabhata Apr 8 '13 at 21:56
• @Aryabhata: Thanks for the comment. It should be ok. – Mhenni Benghorbal Apr 8 '13 at 22:01
• I don't understand. As the answer currently stands, I believe you have it wrong (at least two other answers differ from this) and was pointing that out, before someone comes around and downvotes :-) – Aryabhata Apr 8 '13 at 22:05
• By the way, this answer was posted before other answers. – Mhenni Benghorbal Apr 8 '13 at 22:19
• You can clearly see the times the other answers were posted, Mhenni. For instance, Brian's answer was 14 mins before yours. Perhaps you didn't refresh your page. – Aryabhata Apr 8 '13 at 22:21

Suppose we seek to evaluate $$\sum_{k=0}^n {n\choose k} k^p.$$

Introduce $$k^p = \frac{p!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{p+1}} \exp(kz) \; dz.$$

This yields for the sum $$\frac{p!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{p+1}} \sum_{k=0}^n {n\choose k} \exp(kz) \; dz \\ = \frac{p!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{p+1}} (1+\exp(z))^n \; dz \\ = \frac{p!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{p+1}} (2+\exp(z)-1)^n \; dz \\ = \frac{p!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{p+1}} \sum_{q=0}^n {n\choose q} (\exp(z)-1)^q 2^{n-q} \; dz \\ = \sum_{q=0}^n {n\choose q} \times q! \times 2^{n-q} \times \frac{p!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{p+1}} \frac{(\exp(z)-1)^q}{q!} \; dz.$$

Recall the species equation for labelled set partitions: $$\mathfrak{P}(\mathcal{U}\mathfrak{P}_{\ge 1}(\mathcal{Z}))$$

which yields the bivariate generating function of the Stirling numbers of the second kind $$\exp(u(\exp(z)-1)).$$

Substitute this into the sum to get $$\sum_{q=0}^n {n\choose q} \times q! \times 2^{n-q} \times {p\brace q}$$

Now observe that when $n\gt p$ the Stirling number is zero for the values $p\lt q \le n$ so we may replace $n$ by $p.$ On the other hand when $n\lt p$ the binomial coefficient is zero for the values $n\lt q \le p$ so we may again replace $n$ by $p.$ This finally yields

$$\sum_{q=0}^p {n\choose q} \times q! \times 2^{n-q} \times {p\brace q}$$

as observed by the other contributors.

We have:

$$\sum_{k=0}^n {n\choose k} k^p = \sum_{k=0}^n {n\choose k} \left[\sum_{j=0}^p j! {k\choose j} {p\brace j}\right] = \sum_{j=0}^p j! \left[\sum_{k=j}^n {n\choose k} {k\choose j} \right] {p\brace j} = \sum_{j=0}^p j! 2^{n-j}{n\choose j} {p\brace j} ,$$

with $$p\brace j$$ being the Stirling number of the second kind.