# 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?

• maa.org/sites/default/files/pdf/upload_library/2/… ... page 265 or 14? Dec 3, 2017 at 23:17
• That is a slightly different identity (note that the bounds of summation on the RHS are different in the two identities). Dec 3, 2017 at 23:36
• I cannot find the formula on the wiki pages for both Stirling numbers of the second kind & Faulhaber's Formula, It is definitely remark worthy. Dec 3, 2017 at 23:36
• It turns out what you found actually IS the correct identity, with a typo in the bounds of the RHS summation! Dec 3, 2017 at 23:59

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.

• Nice proof! Do you know if this identity shows up in any interesting work? Dec 4, 2017 at 0:07
• are you interested in this identity in itself or on the sum of $k^p$? Dec 4, 2017 at 1:38
• I'm interested in this identity in itself. Dec 4, 2017 at 6:34
• @RobertAdkins: added some reference, for you to start and dig inside. Dec 4, 2017 at 10:03

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$$

$$(\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.
• Great proof! My proof also uses finite calculus, though a slightly different approach where we use the fact that $\Delta(x^{\underline{m}}) = m x^{\underline{m-1}}$. Dec 4, 2017 at 6:33