Sums of Powers as Sums of Stirling Numbers and Falling Factorials I am able to prove the following identity:
$$\sum_{k = 0}^n k^p = \sum_{j = 0}^p {p \brace j} \frac{(n+1)^\underline{j+1}}{j+1},$$
where $p$ and $n$ are non-negative integers, ${p \brace j} = S(p, j)$ is a Stirling number of the second kind, and $x^\underline{m} = x(x-1)\cdots (x - m + 1)$ is the falling factorial function.
My question: Is this identity commonly known in combinatorics?
 A: That's simply a consequence of the Hockey stick identity for the binomial
$$
\eqalign{
  & \sum\limits_{0\, \le \,k\, \le \,n} {k^{\,p} }  = \sum\limits_{0\, \le \,k\, \le \,n} {\sum\limits_{0\, \le \,j\, \le \,p} {\left\{ \matrix{
  p \cr 
  j \cr}  \right\}k^{\,\underline {\,j\,} } } }  =   \cr 
  &  = \sum\limits_{0\, \le \,j\, \le \,p} {j!\left\{ \matrix{
  p \cr 
  j \cr}  \right\}\sum\limits_{0\, \le \,k\, \le \,n} {{{k^{\,\underline {\,j\,} } } \over {j!}}} }  = \sum\limits_{0\, \le \,j\, \le \,p} {j!\left\{ \matrix{
  p \cr 
  j \cr}  \right\}\sum\limits_{0\, \le \,k\, \le \,n} {\left( \matrix{
  k \cr 
  j \cr}  \right)} }  =   \cr 
  &  = \sum\limits_{0\, \le \,j\, \le \,p} {j!\left\{ \matrix{
  p \cr 
  j \cr}  \right\}\left( \matrix{
  n + 1 \hfill \cr 
  j + 1 \hfill \cr}  \right)}  = \sum\limits_{0\, \le \,j\, \le \,p} {j!\left\{ \matrix{
  p \cr 
  j \cr}  \right\}{{\left( {n + 1} \right)^{\,\underline {\,j + 1\,} } } \over {\left( {j + 1} \right)!}}}  =   \cr 
  &  = \sum\limits_{0\, \le \,j\, \le \,p} {\left\{ \matrix{
  p \cr 
  j \cr}  \right\}{{\left( {n + 1} \right)^{\,\underline {\,j + 1\,} } } \over {j + 1}}}  \cr} 
$$
The "Summa Potestatum" ($\sum\limits_{0\, \le \,k\, \le \,n} {k^{\,p} }$)
has been the subject of many works, by various great Mathematicians over the centuries, in modern times 
starting with Bernoulli.
So there is a vast literature, resulting in many different formulations, some of which are
$$
\eqalign{
  & S_m (n) = \sum\limits_{0\, \le \,k\, \le \,n - 1} {k^{\,m} } \quad \left| {\;0 \le {\rm integer }m,n} \right. =   \cr 
  &  = \sum\limits_{\left( {0\, \le } \right)\,j\,\left( { \le \,m} \right)} {\left\langle \matrix{
  m \cr 
  j \cr}  \right\rangle \left( \matrix{
  n + j \cr 
  m + 1 \cr}  \right)}  = \sum\limits_{\left( {0\, \le } \right)\,j\,\left( { \le \,m} \right)} {\;j!\;\left\{ \matrix{
  m \cr 
  j \cr}  \right\}\left( \matrix{
  n \cr 
  j + 1 \cr}  \right)}  =   \cr 
  &  = {1 \over {m + 1}}\sum\limits_{0\, \le \,j\, \le \,m} {\left( \matrix{
  m + 1 \cr 
  j \cr}  \right)\;B(j)\;n^{\,m + 1 - j} }  \cr} 
$$
where the angle brackets denotes the Eulerian Numbers 1st kind, the curly brackets the Stirling Numbers 2nd kind, and $B(j)$ the Bernouilli Numbers.
Thus in some of the papers on the subject you can find the relation with the Stirling Numbers,
for instance in the renowned "Concrete Mathematics", pag. 289.
A: I don't have a reference off the top of my head, but this is a straightforward application of the calculus of finite differences and I expect it's well known in some form or another. Here's one way to structure the proof.
The key player is the forward difference operator, which takes as input a sequence $a_n$ and returns as output the sequence
$$(\Delta a)_n = a_{n+1} - a_n.$$

Claim 1: $\displaystyle \Delta {n \choose k} = {n \choose k-1}$ (a restatement of Pascal's identity).

The sequences $n \mapsto {n \choose k}$ have the following remarkable property: every sequence can be written uniquely as an infinite sum
$$a_n = \sum_{k \ge 0} c_k {n \choose k}$$
and we can determine the coefficients $c_k$ as follows: taking forward differences $i$ times gives
$$(\Delta^i a)_n = \sum_{k \ge i} c_k {n \choose k-i}$$
and substituting $n = 0$ gives
$$(\Delta^k a)_0 = c_k.$$
(This should remind you a lot of computing coefficients of a Taylor series by differentiating.) Hence:

Claim 2: If $a_n$ is any sequence, then
$$a_n = \sum_{k \ge 0} (\Delta^k a)_0 {n \choose k}.$$

(Various alternate proofs of this result are possible. I think there are two ways to do this using generating functions, and you can also do it by writing $\Delta$ in terms of the shift operator $(Sa)_n = a_{n+1}$.)
Note that this sum terminates if and only if $a_n$ is a polynomial in $n$.
Now, instead of computing the "finite derivative" $\Delta$ of a sequence, we want to compute the "finite integral," namely
$$(\Sigma a)_n = a_0 + a_1 + \dots + a_n.$$
The two are related by the "fundamental theorem of finite calculus," which is just the observation that $(\Delta \Sigma a)_n = a_{n+1}$. This leads to:

Claim 3: $\displaystyle \Sigma {n \choose k} = {n+1 \choose k+1}$ (a restatement of the hockey stick identity).

This lets us compute the "finite integral" of any sequence given the sequence of all of its finite differences: writing
$$a_n = \sum_{k \ge 0} (\Delta^k a)_0 {n \choose k}$$
and applying $\Sigma$ to both sides gives
$$(\Sigma a)_n = \sum_{k \ge 0} (\Delta^k a)_0 {n+1 \choose k+1}.$$
(This should remind you of integrating a Taylor series term by term.)
It remains to compute the finite differences $(\Delta^k a)_0$ in the particular case that $a_n = n^p$. At this point it will be convenient to introduce the shift operator $S$ mentioned above so we can write $\Delta = S - I$, giving
$$\Delta^k = \sum_{i=0}^k (-1)^{k-i} {k \choose i} S^i$$
which leads to
$$(\Delta^k a)_0 = \sum_{i=0}^k (-1)^{k-i} {k \choose i} a_i.$$
Substituting $a_n = n^p$ gives one of the well-known formulas for Stirling numbers of the second kind, up to a factorial factor.
This entire argument can be recast in terms of generating functions as well.
