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