5
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ maa.org/sites/default/files/pdf/upload_library/2/… ... page 265 or 14? $\endgroup$ Dec 3, 2017 at 23:17
  • $\begingroup$ That is a slightly different identity (note that the bounds of summation on the RHS are different in the two identities). $\endgroup$
    – radkins
    Dec 3, 2017 at 23:36
  • $\begingroup$ 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. $\endgroup$ Dec 3, 2017 at 23:36
  • $\begingroup$ It turns out what you found actually IS the correct identity, with a typo in the bounds of the RHS summation! $\endgroup$
    – radkins
    Dec 3, 2017 at 23:59

2 Answers 2

5
$\begingroup$

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.

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

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.

$\endgroup$
1
  • $\begingroup$ 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}}$. $\endgroup$
    – radkins
    Dec 4, 2017 at 6:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .