Integer sum as binomial coefficient

Question

What's the rule for expressing integer sums as binomial coefficients? That is, for $p=1$ it is $$\sum_{n=1}^N n^p = {{N+1}\choose 2} $$ What is it for higher powers?

Answer 1

There are multiple ways to express the power sum in terms of binomial coefficients. Besides the Bernoulli numbers, as some have mentioned in the comments, here's a way that uses the Stirling numbers of the second kind $\left \{n \atop k \right\}$. These count the number of ways to distribute $n$ objects into $k$ nonempty subsets.

$$ \sum_{n=1}^N n^p = \sum_{k=1}^p \binom{N+1}{k+1} \left\{ p \atop k \right\} k! .$$

Proof. How many functions $f$ are there from the set $\{1, 2, \ldots, p+1 \}$ to the set $\{1, 2, \ldots, N+1\}$ such that $f(1) > f(j)$ for any $j \in \{2, \ldots, p+1\}$?

Answer 1: Condition on the value of $f(1)$. If $f(1) = n+1$, then there are $n$ choices for $f(2)$, $n$ choices for $f(3)$, etc., for a total of $n^p$ functions. Summing over all possible values of $n$ gives the left side.

Answer 2: Condition on the number of elements in the range of $f$. If the range of $f$ has $k+1$ elements, there are $\binom{N+1}{k+1}$ ways to choose exactly which elements will comprise the range. The largest of these must be $f(1)$, and the remaining $p$ elements in the domain must be mapped to the other $k$ elements in the range. There are $\left \{ p \atop k \right\}$ ways to assign the remaining $p$ elements to $k$ nonempty groups, and then $k!$ ways to assign these groups to the actual $k$ remaining elements in the range. (More generally, the number of onto functions from a $p$-set to a $k$-set is $\left \{ p \atop k \right\} k!$.) Summing over all possible values of $k$ gives the right side.

Answer 2

$\def\str#1#2{\left\{#1\atop#2\right\}}$ Let $\str{n}{m}$ be the Stirling number of the second kind, It can be defined by the formula $$ X^p=\sum_{m=0}^p\str{p}{m}X(X-1)\cdots(X-m+1)\tag 1 $$ This implies that $$\eqalign{ n^p&=\sum_{m=0}^p m!\str{p}{m}\binom{n}{m}\tag 2\cr &=\sum_{m=0}^p m!\str{p}{m}\left(\binom{n+1}{m+1} -\binom{n}{m+1}\right)\cr } $$ So, taking the sum for $n=1,2,\ldots,N$ we get $$ \sum_{n=1}^Nn^p=\sum_{m=0}^pm!\str{p}{m}\left(\binom{N+1}{m+1} -\binom{1}{m+1}\right) $$ Noting that $\str{p}{0}=0$ for $p>0$ we conclude that $$ \sum_{n=1}^Nn^p=\sum_{m=1}^pm!\str{p}{m} \binom{N+1}{m+1} $$ For $p=1$, we have $\str{1}{1}=1$, and we get the OP's formula. For $p=2$ we have $\str{2}{1}=1$ and $\str{2}{2}=1$, $$ \sum_{n=1}^Nn^2= \binom{N+1}{2} +2\binom{N+1}{3} $$ and for $p=3$ we have $\str{3}{1}=1$, $\str{3}{2}=3$ and $\str{3}{3}=1$, hence $$ \sum_{n=1}^Nn^3= \binom{N+1}{2} + 6 \binom{N+1}{3} +6 \binom{N+1}{4} . $$