Sums $\sum_{k = 0}^n k^t {n \choose k}$ where $t$ is a positive integer

Question

I recently came across the problem of finding out the sum $\sum_{k = 0}^n k^2 {n \choose k}$. The solution that I've found goes something like this: $\sum_{k = 0}^n k^2 {n \choose k}=\sum_{k = 0}^n k(k-1) {n \choose k} + \sum_{k = 0}^n k {n \choose k}$. Using the fact that $\sum_{k = 0}^n k {n \choose k}=n2^{n-1}$ and that $\sum_{k = 0}^n k(k-1) {n \choose k} =[\sum_{k = 0}^n (x^k)'' {n \choose k}]|_{x=1}=[\sum_{k = 0}^n (x^k) {n \choose k}]'' |_{x=1}=[(x+1)^n]'' |_{x=1} = n(n-1)2^{n-2}$

(where we use the binomial expansion $(x+1)^n=\sum_{k = 0}^n x^k {n \choose k}$), one can easily evaluate the desired sum as being equal to $n(n+1)2^{n-3}$.

Clearly, one can continue this method to find (recursively) formulas for the sums $\sum_{k = 0}^n k^t {n \choose k}$ where $t$ is a positive integer. For example, one more iteration gives $\sum_{k = 0}^n k^3 {n \choose k}=n^2(n+3)2^{n-3}$ (if I did not made any calculation error).

So, if we define $F(t)$ to be the polynomial such that $\sum_{k = 0}^n k^t {n \choose k} = 2^{n-t} F(t)$, my question is simply:

Is there a closed formula for $F(t)$?

Also, I would be happy with any reference on this kind of sums. Thank you!

Answer 1

By using Stirling numbers of the second kind we have that: $$ k^t = \sum_{j=0}^{t}j!{t \brace j}\binom{k}{j} $$ hence: $$\sum_{k=0}^n k^t \binom{n}{k} = \sum_{j=0}^{t}{t \brace j}\sum_{k=0}^{n}j!\binom{k}{j}\binom{n}{k}\tag{1}$$ but since: $$\sum_{k=0}^{n}\binom{k}{j}\binom{n}{k} = 2^{n-j}\binom{n}{j}\tag{2}$$ it follows that:

$$\sum_{k=0}^n k^t \binom{n}{k}=2^{n-t}\sum_{j=0}^{t}{t\brace j}\,2^{t-j}\,(n)_j \tag{3}$$

where $(n)_j$ is the falling Pochhammer symbol $(n)_j = n\cdot(n-1)\cdot\ldots\cdot(n-j+1)=j!\binom{n}{j}$.

Answer 2

I greatly prefer to avoid monomials when doing summation, because they don't behave very well (though for integrals, they're just perfect). On the other hand, if we use $1, {x\choose 1}, {x\choose 2},\ldots$ instead of $1,x,x^2,\ldots$, we tend to get much cleaner results. If we need to, we can take linear combinations to get the result for monomials (this is exactly how the Stirling numbers arise in Jack's solution).

To illustrate, let's calculate $\sum_{k=0}^n {k\choose t}{n\choose k}$. This counts the number of ways of selecting, from $n$ players, two disjoint teams, the second of which has size $t$—first we pick the $k$ players not on the first team, then we pick the $t$ players on the second team from those. So $\sum_{k=0}^n {k\choose t}{n\choose k} = 2^{n-j} {n\choose j}$.

Now, say we want to find $\sum_{k=0}^n k^2 {n\choose k}$. We have $k^2 = 2 {k\choose 2} + {k \choose 1}$, so: $$\sum_{k=0}^n k^2 {n\choose k} = 2\sum_{k=0}^n {k\choose 2} {n\choose k} + \sum_{k=0}^n {k\choose 1} {n\choose k}$$ $$=2\cdot 2^{n-2}{n\choose 2} + 2^{n-1} {n\choose 1}$$ $$= 2^{n-1} \left({n\choose 2}+{n\choose 1}\right) $$ $$=2^{n-1} {{n+1}\choose 2}$$

Answer 3

This is closely related to Jack D'Aurizio's answer, but I thought it worth linking to some other related questions.

---

As I've used in several related posts (e.g. here, here, and in the this closely related answer), each power of $k$ can be written as a sum of binomial coefficients considered as polynomials (combinatorial polynomials) $$ \newcommand{\stirtwo}[2]{\left\{{#1}\atop{#2}\right\}} k^m=\sum_{j=0}^m\binom{k}{j}\,\stirtwo{m}{j}j!\tag{1} $$ where $\stirtwo{m}{j}$ is a Stirling Number of the Second Kind. We also have $$ \binom{n}{k}\binom{k}{j}=\binom{n}{j}\binom{n-j}{k-j}\tag{2} $$ which is easily shown by expanding the binomial coefficients into factorials.

Thus, $$ \begin{align} \sum_{k=0}^n\binom{n}{k}k^m &=\sum_{k=0}^n\sum_{j=0}^m\binom{n}{k}\binom{k}{j}\,\stirtwo{m}{j}j!\\ &=\sum_{k=0}^n\sum_{j=0}^m\binom{n}{j}\binom{n-j}{k-j}\,\stirtwo{m}{j}j!\\ &=\sum_{j=0}^m\binom{n}{j}2^{n-j}\stirtwo{m}{j}j!\\ &=2^{n-m}\color{#C00000}{\sum_{j=0}^m\binom{n}{j}2^{m-j}\stirtwo{m}{j}j!}\\ &=2^{n-m}\color{#C00000}{P_m(n)}\tag{3} \end{align} $$ where $P_m$ is a degree-$m$ polynomial. The sum in red is as close to a closed form for $P_m$ as I have seen.

Answer 4

$\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ $\ds{t = 1,2,3,\ldots}$ and $\ds{0 < a < 1}$:

\begin{align} \color{#66f}{\large\sum_{k = 0}^{n}k^{t}{n \choose k}}& =\sum_{k = 1}^{\infty}k^{t}{n \choose n - k} =\sum_{k = 1}^{\infty}k^{t}\oint_{\verts{z}\ =\ a} {\pars{1 + z}^{n} \over z^{n - k + 1}}\,{\dd z \over 2\pi\ic} \\[3mm]&=\oint_{\verts{z}\ =\ a}{\pars{1 + z}^{n} \over z^{n + 1}} \sum_{k = 1}^{\infty}{z^{k} \over k^{-t}}\,{\dd z \over 2\pi\ic} =\oint_{\verts{z}\ =\ a}{\pars{1 + z}^{n} \over z^{n + 1}} {\rm Li}_{-t}\pars{z}\,{\dd z \over 2\pi\ic} \\[3mm]&=\oint_{\verts{z}\ =\ a}{\pars{1 + z}^{n} \over z^{n + 1}} \pars{-1}^{t}\sum_{\ell = 0}^{t}\pars{-1}^{\ell}{\rm S}\pars{t + 1,\ell + 1} \pars{1 - z}^{-\ell - 1}\,{\dd z \over 2\pi\ic} \end{align} where $\ds{{\rm S}\pars{n,k}}$ are the Stirling Numbers of the Second Kind.

\begin{align} \color{#66f}{\large\sum_{k = 0}^{n}k^{t}{n \choose k}}& =\pars{-1}^{t}\sum_{\ell = 0}^{t}\pars{-1}^{\ell}{\rm S}\pars{t + 1,\ell + 1} \times \\[3mm]&\sum_{\ell' = 0}^{\infty}{-\ell - 1 \choose \ell'} \pars{-1}^{\ell'}\oint_{\verts{z}\ =\ a}{\pars{1 + z}^{n} \over z^{n - \ell' + 1}} \,{\dd z \over 2\pi\ic} \\[3mm]&=\pars{-1}^{t}\sum_{\ell = 0}^{t}\pars{-1}^{\ell}{\rm S}\pars{t + 1,\ell + 1}\sum_{\ell' = 0}^{n}{\ell + \ell' \choose \ell'} {n \choose \ell'} \\[3mm]&=\color{#66f}{\large\pars{-1}^{t}\sum_{\ell = 0}^{t}\pars{-1}^{\ell} {\rm S}\pars{t + 1,\ell + 1}\ _{2}{\rm F}_{1}\pars{1 + \ell,-n;1;-1}} \end{align}

Answer 5

Another possible answer is found using generating functions. The answer is then given by the coefficient of $x^n$ (or of $x^n/n!$ in the case of the exponential generating function).

Let us write $a_{n,t}=\sum_{k=0}^nk^t\binom nk$ and define $$f_t(x)=\sum_{n=0}^\infty a_{n,t}x^n =\sum_{n=0}^\infty\sum_{k=0}^nk^t\binom nkx^n.$$ Reorder the sums and get $$f_t(x)=\sum_{k=0}^\infty\sum_{n=k}^\infty k^t\binom nkx^n =\sum_{k=0}^\infty k^t\frac{x^k}{(1-x)^{k+1}}=\frac1{1-x}\Phi\left(\frac x{1-x},-t,0\right)$$ where $\Phi$ is the Lerch transcendant function.

The exponential generating function $$g_t(x)=\sum_{n=0}^\infty a_{n,t}\frac{x^n}{n!}=\mathrm e^{2x}B_t(x)$$ is found using the same method. $B_t$ is the Bell polynomial of order $t$.