Is there any closed form for $\sum_{k=0}^{n}k^{r}\binom{n}{k}$?

Question

Is there any elementary way to derive a closed form for the following sum:

$$\sum_{k=0}^{n}k^{r}\binom{n}{k}$$

Where $r$ is a fixed number.

I tried like that:

$$\left(1+x\right)^{n}=\sum_{k=0}^{n}\binom{n}{k}x^{k}$$ Taking the derivative of both sides with respect to $x$ yields:

$$n\left(1+x\right)^{\left(n-1\right)}=\sum_{k=0}^{n}\binom{n}{k}kx^{\left(k-1\right)}$$

Multiplying both sides by $x$:

$$xn\left(1+x\right)^{\left(n-1\right)}=\sum_{k=0}^{n}\binom{n}{k}kx^{k}$$

Again taking the derivative of both sides with respect to $x$: $$n\left(1+x\right)^{\left(n-1\right)}+xn\left(n-1\right)\left(1+x\right)^{\left(n-2\right)}=\sum_{k=0}^{n}\binom{n}{k}k^{2}x^{\left(k-1\right)}$$

But I don't know if repeating this process will give us a good closed form (if I was sure then finally we just need to set $x=1$ to get what we want).

I know the answer when $r=0$ and that easily can be derived , but the exponential $r$ is something that prevents me of computing, any hint is appreciated.

Answer 1

Use moments of binomial distribution

$$E_p(X^r)=\sum_{x=0}^{n} x^r \binom{n}{x} p^x (1-p)^{n-x} $$

for $p=.5$

$$\sum_{x=0}^{n} x^r \binom{n}{x}=2^n E_{p=.5}(X^r).$$

For $E(X^r)$ see Knoblauch (2008).

Answer 2

We can find a representation in terms of falling factorials of $n$. Let $r$ be a positive integer. We can represent $k^r$ in terms of Stirling numbers of the second kind: \begin{align*} k^r=\sum_{j=1}^r{r\brace j}k^{\underline{j}}\tag{1} \end{align*} with falling factorials $k^{\underline{j}}=k(k-1)\cdots(k-j+1)$.

We obtain \begin{align*} \color{blue}{\sum_{k=0}^n\binom{n}{k}k^r}&=\sum_{k=1}^n\binom{n}{k}\sum_{j=1}^r{r\brace j}k^{\underline{j}}\tag{2}\\ &=\sum_{j=1}^r{r\brace j}\sum_{k=j}^n\binom{n}{k}k^{\underline{j}}\\ &=\sum_{j=1}^r{r\brace j}n^{\underline{j}}\sum_{k=j}^n\binom{n-j}{k-j}\tag{3}\\ &=\sum_{j=1}^r{r\brace j}n^{\underline{j}}\sum_{k=0}^{n-j}\binom{n-j}{k}\tag{4}\\ &\,\,\color{blue}{=\sum_{j=1}^r2^{n-j}{r\brace j}n^{\underline{j}}} \end{align*}

Comment:

• In (2) we substitute $k^r$ according to (1).

• In (3) we use the binomial identity $\binom{p}{q}=\frac{p}{q}\binom{p-1}{q-1}$.

• In (4) we shift the index to start with $j=0$.

Note: With regard to a comment we derive a representation from which we might conclude, that a closed form is not within reach.

We use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ in a series. This way we can write for instance, recalling the Taylor series representation of $e^z=\sum_{n=0}^\infty \frac{z^n}{n!}$: \begin{align*} r![z^r]e^{kz}=k^r\tag{5} \end{align*}

We obtain using (5) \begin{align*} \sum_{k=0}^n\binom{n}{k}k^r&=\sum_{k=0}^n\binom{n}{k}r![z^r]e^{kz}\\ &=r![z^r]\sum_{k=0}^n\binom{n}{k}\left(e^z\right)^k\\ &=r![z^r]\left(1+e^z\right)^n\\ &=r![z^r]\left(2+z+\frac{z^2}{2}+\frac{z^3}{6}+\cdots+\frac{z^r}{r!}\right)^n \end{align*} The last line indicates that extraction of the coefficient of $z^r$ in closed form is not feasible.