# Integer sum as binomial coefficient

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?

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