8
$\begingroup$

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

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

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

$\endgroup$
  • $\begingroup$ Interesting approach. Am I right in concluding this is roughly the same argument as in Michael's solution above? $\endgroup$ – oldrinb Apr 8 '13 at 21:47
  • $\begingroup$ @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/… $\endgroup$ – Aryabhata Apr 8 '13 at 21:48
  • $\begingroup$ thanks for that... I haven't been exposed to this before! $\endgroup$ – oldrinb Apr 8 '13 at 21:50
  • $\begingroup$ In your formula, is it $s(p,k)$ or s(k,p)? $\endgroup$ – Mhenni Benghorbal Apr 8 '13 at 22:11
  • $\begingroup$ @MhenniBenghorbal: $s(p,k)$, same as what you have. $\endgroup$ – Aryabhata Apr 8 '13 at 22:13
8
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Elegant and concise -- too good! Pretty neat. $\endgroup$ – oldrinb Apr 8 '13 at 21:55
  • $\begingroup$ @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? $\endgroup$ – Aryabhata Apr 8 '13 at 22:01
  • $\begingroup$ @Aryabhata true, I was just surprised by how concise this was. $\endgroup$ – oldrinb Apr 8 '13 at 22:02
  • $\begingroup$ Of course, we could write it as an integral (Cauchy's formula), so +1 to this answer. $\endgroup$ – Aryabhata Apr 8 '13 at 22:03
  • $\begingroup$ @Aryabhata: The closed form that you have will follow from this, use $e^x+1=e^x-1+2$. (+1) on your answer! $\endgroup$ – Sungjin Kim Apr 8 '13 at 22:08
5
$\begingroup$

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

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

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.

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

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.

$\endgroup$
  • $\begingroup$ You might be missing a $2^{-k}$ factor inside the $\sum$. $\endgroup$ – Aryabhata Apr 8 '13 at 21:56
  • $\begingroup$ @Aryabhata: Thanks for the comment. It should be ok. $\endgroup$ – Mhenni Benghorbal Apr 8 '13 at 22:01
  • $\begingroup$ 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 :-) $\endgroup$ – Aryabhata Apr 8 '13 at 22:05
  • $\begingroup$ By the way, this answer was posted before other answers. $\endgroup$ – Mhenni Benghorbal Apr 8 '13 at 22:19
  • $\begingroup$ 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. $\endgroup$ – Aryabhata Apr 8 '13 at 22:21
1
$\begingroup$

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.

$\endgroup$

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.