Eulerian number identity

Here's a proof of the identity. Unfortunately, it doesn't show how anyone would come up with this formula. Like the proofs referred to in the comments, this proof is based on the beta integral $$\int_0^1 u^m (1-u)^{n-m}\, du = \frac{m!\,(n-m)!}{(n+1)!} = \frac{1}{(n+1)\binom{n}{m}}.$$

By the generating function for the Eulerian numbers, which can be found in the Wikipedia article (https://en.wikipedia.org/wiki/Eulerian_number), we have $$ 1+\sum_{n=1}^\infty \frac{x^n}{n!} \sum_{m=0}^{n-1} A(n,m) t^m = \frac{t-1}{t-e^{(t-1)x}}. $$ Replacing $t$ with $-u/(1-u)$ and $x$ with $x(1-u)$, and simplifying, gives $$ 1+\sum_{n=1}^\infty \frac{x^n}{n!} \sum_{m=0}^{n-1} (-1)^m A(n,m) u^m (1-u)^{n-m} = \frac{e^x}{1+(e^x-1)u}. $$ Integrating with respect to $u$ from 0 to 1 gives $$ 1+\sum_{n=1}^\infty \frac{x^n}{n!} \sum_{m=0}^{n-1} (-1)^m \frac{A(n,m)}{(n+1) \binom nm}=e^x\frac{x}{e^x-1} =1+\frac{x}{2}+\sum_{n=2}^\infty B_n \frac{x^n}{n!}. $$

.....sometimes, snorkeling in a turquoise ocean, relaxed and contemplating the colourful and familiar inhabitants of the sea, all of a sudden strange creatures emerge from the deep, arousing strangeness, shudder and bewilderment. Then either they dissappear again after a while, leaving behind a faint memory of uneasiness fading with time, or, upon closer scrutiny and aquaintance with the properties of their natural environment, they become as natural and peaceful to the mind as all those creatures hitherto known to one. In other words, there is a way to place your unnamed identity into a natural environment as to make its appearance completely obvious, and this has to do with some very classical and concrete mathematics (with the pun to Graham et al. intended). Thus it shows how someone could come up with this formula, and in demonstrating this we proceed in the classical analytic way: Thesis – Antithesis – Synthesis.

Thesis First of all, you have to place all participants of your identity into their natural home. Now your Eulerian numbers, as you define them, are far away from home – one reason for this being that your definition is combinatorial, whereas it is difficult to find a natural combinatorial definition of their counterparts, the Bernoulli numbers which you wish them to relate to, because of their being noninteger rational numbers–. To assign them to their natural home one has, as their name suggests, to direct one’s attention to their founding father, the great Leonhard Euler. So on one wonderful day in midst eighteenth century, Herr Euler decided, for reasons hinted at below, to get interested in finding a rational expression for the formal power series \begin{equation*} P_n(x):=\sum_{k=0}^{\infty} k^n x^k \quad,\quad \text{with $n$ fixed, but arbitrary.}\tag{0} \end{equation*} And thus he achieved this: he started with the identity \begin{equation*} 1+x+x^2+x^3+\cdots = \dfrac{1}{1-x},\tag{1} \end{equation*} differentiated it and multiplied it with $x$, obtaining thus \begin{equation*} x+2x^2+3x^3+\cdots = \dfrac{x}{(1-x)^2}, \end{equation*} differentiated it and multiplied it with $x$, obtaining thus $$ x+2^2x^2+3^2x^3+\cdots = \dfrac{x^2+x}{(1-x)^3}, $$ differentiated it and multiplied it with $x$, obtaining thus $$ x+2^3x^2+3^3x^3+\cdots = \dfrac{x^3+4x^2+x}{(1-x)^4}, $$ and so on, arriving at his sought-for rational expression \begin{equation*} \fbox{$0^nx^0+1^nx^1+2^nx^2+3^nx^3+\cdots = \sum_{k=0}^{\infty} k^n x^k = \dfrac{A_n(x)}{(1-x)^{n+1}}$} \tag{2} \end{equation*} (with the prescription $0^n:=[n=0)]$), where $A_n(x) := \sum_{k=0}^n A(n,k)x^k$ are monic polynomials, called the Eulerian polynomials, whose nature reveals itself by contemplating the step $n-1 \rightarrow n$: write down this formula for $ n-1$, differentiate it and multiply by $x$, thus arriving at the recursion \begin{equation*} A_n(x) = x(1-x)A_{n-1}'(x) + nxA_{n-1}(x) \quad,\quad A_0(x) = 1.\tag{3} \end{equation*} This puts the Eulerian numbers $A(n,k)$ into their natural home as the coefficients of the Eulerian polynomials. From (3) it is straightforward to derive their recursion $$\tag{3a} A(n,k) = kA(n-1,k)+(n-k+1)A(n-1,k-1) \quad,\quad A(0,0) = 1, $$ and from (2) the explicit formula $$ A(n,k) = \sum_{i=0}^k (-1)^i\binom{n+1}{i} (k-i)^n = \sum_{j=0}^k (-1)^{k-j}\binom{n+1}{k-j} j^n. $$ (That this definition of the Eulerian numbers coincides with yours combinatorial one – up to an index shift, see the Remark below – is by no means obvious and one of the many strange ways mathematics take; it is mainly due to the fact that, ominously, the number of $n$-permutations having $k+1$ descents obey the same recursion law (3a) as the Eulerian numbers.) So our working definition of the Eulerian numbers $A(n,k)$ is

Definition The Eulerian numbers $A(n,k), n,k \in \mathbb{N}$, are defined by $$ \fbox{$A(n,k) := \text{coefficient of $x^k$ in the Eulerian polynomial $A_n(x)$.}$} $$ Antithesis Now to the next species, the Bernoulli numbers $B_n$. Their natural home is the arena of the century old battle for finding a closed formula for the power sums \begin{equation*} S_n(k) := 1^n+2^n+3^n+\cdots +k^n = \sum_{j=1}^k j^n\tag{4}. \end{equation*} The first instances were known throughout the centuries and to countless scholars tormented with pointless inductions: $$ \begin{split} S_1(k) & = \dfrac{1}{2}k^{2} + \dfrac{1}{2}k = \dfrac{k(k+1)}{2};\\ \newline S_2(k) & = \dfrac{1}{3}k^{3} + \dfrac{1}{2}k^{2} + \dfrac {1}{6}k^{\phantom{1}} = \dfrac{k(k+1)(2k+1)}{6}\\ \newline & = \dfrac{(2k)(2k+1)(2k+2)}{24}; \\ \newline S_3(x) & = \dfrac{1}{4}k^{4} + \dfrac{1}{2}k^{3} + \dfrac{1}{4}k^{2} = \dfrac{k^2(k+1)^2}{4}. \end{split} $$ What these first instances lead one to conjecture, is true – $S_n(k)$ is a polynomial in $k$ of degree $n+1$ with leading term $\dfrac{k^{n+1}}{n+1}$ and no constant term; this is easily proved by an ingenious telescoping argument due to Pascal. Replacing $k$ by an indeterminate $x$ this gives the power sum polynomials $S_n(x)$, and one of the Holy Grails of mathematics for centuries was to exhibit a closed formula for these power sum polynomials.

Things acquired momentum in the seventeenth century where Calculus was lying in the air and the desire grew to compute the areas or volumes of everything one could lay one's greedy claws on, and in the course of these events suspicion grew that the key to a closed formula for the $S_n(x)$ lay in other time-withered remnants of traditional lore bestowed upon us by the ancient ones - the figurate numbers. These were already known to the Pythagoreans, since they fitted well to their belief of a mythical unity of number and form– algebra and geometry, in modern terms –, and this fundamental dichotomy is alive and in best shape today in form of the hot topic called Arithmetc Geometry. Not turning quite so big wheels, they coined the concept of figurate numbers, numbers given by the number of elements of elementary well-known geometric configurations, like pebbles on the beach, say. Ordered by dimension $n$, they formed familes $F(k,n) = F_n(k)$, $k=1,2 ,3,\dots$ as follows:

• $n=0$, $F(k,0)$: in dimension 0, there is no place to move and you can place the pebbles just one at a time, so

  $F(k,0) = 1, 1, 1, \dots$

• $n=1$, $F(k,1)$: in dimension 1, you can put one pebble after the other in line, one at a time, and so you build the naturals:

  $F(k,1) = 1, 1+1=2, 1+1+1=3, \dots$

• $n=2$, $F(k,2)$: in dimension 2, you have room to pile the patterns of dimension 1 on top of each other in a plane in triangular shapes, and so you build the triangular numbers:

  $F(k,2) = 1, 1+2=3, 1+2+3=6, \dots$

• $n=3$, $F(k,3)$: in dimension $3$, you have room to pile the patterns of dimension 2 on top of each other in space in tetraedrical shapes, and so you build the triangular pyramidal or tetrahedral numbers:

  $F(k,3) = 1, 1+3=4, 1+3+6=10, \dots$

From there on, visualization breaks down, but the pattern should be clear: the figurate numbers $F(k,n)$ confirm to the recursion \begin{equation*} F(k,n) = \sum_{j=1}^k F(j,n-1) \quad,\quad F(k,0) = 1. \tag{5} \end{equation*} Another Holy Grail of the ancient times was to give a closed formula for the figurate numbers $F(k,n)$. Such a formula was found, then forgotten, then rediscovered once and again; this colourful and interesting story is told in [1]. At any rate, the answer is, in modern terms, \begin{equation*} \fbox{$F(k,n) = \dbinom{k+n-1}{n}$},\tag{6} \end{equation*} which, as we will see, comprises the key to paradise.

At this point, things begin to become interesting. The $F(k,n)$ are polynomials in $k$ of degree $n$, and (5) reads, because of (6), \begin{equation*} \binom{k+n-1}{n} = \sum_{j=1}^k \binom{j+n-2}{n-1},\tag{7} \end{equation*} and this is a closed expression for a sum analogous to (4), namely the accumulated sum of the values of a polynomial of degree $n$ at ascending arguments. And more to that, it is the key to the Holy Grail pertaining to (4), or at least, partly, since it leads to a recursion for a closed form of the power sum polynomials. To see this, let us take a closer look at the first instances of (7): first rewrite (7) as $$ \dfrac{(k+n-1)(k+n-2) \cdots k}{1\cdot 2 \cdots n} = \sum_{j=1}^k \dfrac{(j+n-2)(j+n-3) \cdots j}{1\cdot 2 \cdots (n-1)}. $$ For $n=2,3,4,\dots$ this gives the following equations by expanding the numerators under the sum sign: $$ \begin{split} \dfrac{(k+1)k}{1\cdot2} &= \sum_{j=1}^k \dfrac{j}{1}\\ \newline &= S_1(k)\\ \newline \dfrac{(k+2)(k+1)k}{1\cdot2\cdot3} &= \sum_{j=1}^k \dfrac{(j+1)j}{1\cdot2} \\ \newline &=\dfrac{1}{2}S_2(k)+\dfrac{1}{2}S_1(k)\\ \newline \dfrac{(k+3)(k+2)(k+1)k}{1\cdot2\cdot3\cdot4} &= \sum_{j=1}^k \dfrac{(j+2)(j+1)j}{1\cdot2\cdot3}\\ \newline &= \dfrac{1}{6}S_3(k)+\dfrac{1}{2}S_2(k)+\dfrac13S_1(k) \end{split} $$ and so on, yielding a triangular system for the $S_n(k)$, which can then be recursively solved. This system of three equations, for instance, yields the expressions for $S_1(k), S_2(k), S_3(k)$ given above.

So this detour via the figurated numbers was a possible route to the Holy Grail of a closed espression for the power sums. Time was ripe in the seventeenth century for this approach, it was recognized and taken by many a one like Fermat, Pascal, Wallis, and Jakob Bernoulli, although none of them walked the road to the end – Fermat announced in letters to Mersenne and Roberval autumn 1636 (see [4]) that he had proved (6) and that this had enabled him to solve the general power sum problem, but otherwise, as was his wont, gave no further details; Pascal, in his famous Traité du triangle arithmétique, published 1665, also had (6), but then went his own way for a recursive solution of the power sum problem by providing his celebrated telescoping argumen (still founded on binomials, of course); Wallis, in his Arithmetica Infinitorum of 1656 used the method sketched above to obtain $S_n(k)$ up to order 4, saying one could proceed further this way “as far as one likes”.

And then enter Jakob Bernoulli with his magnum opus where he laid the foundations of modern probability theory, Ars conjectandi, posthumously published in 1713 (for an annotated english translation see [5]). There, in Part II, he begins with a careful description of the combinatorial foundations of his enterprise, the number of “combinations of distinct elements of a given exponent” as he called them – just the binomial coefficients, as we would say today, the number of ways to choose $k$ elements from $n$ given ones – and from the start he links them to the property (5) of the figurate numbers by systematically generating them in increasing order of the exponents and arranging them in a familiar pattern, which can be seen in loc.cit on the bottom of p. 87. (very strange that he does not mention Pascal here). After some elaborations on figurate numbers – where he provides, among other things, a proof of (6) in the verbose Fermat-Pascal style (since Fermat was rather reticent in disclosing details, “verbose” here refers to the way of formulating results, which was cumbersome and done in natural language due to the lack of a developed system of mathematical notation as we have today) – he turns, in a scholium (loc.cit, pp. 95-99) to the power sum problem and Wallis' treatment of it, for whatever reason, and uses the above recursion via the figurate numbers, as did Wallis, to push forward the computation of the $S_n(k)$, going far beyond Wallis until $n=10$ (see loc.cit, p. 96). If he had pursued this road to the end, he might have landed at the full recursion scheme sketched above involving the Stirling numbers of the first kind and at its inversion leading to the closed formula of the $S_n(k)$ in terms of linear combinations of binomials with coefficients the Stirling numbers of the second kind, but these numbers were in 1713 still awaiting their discovery by James Stirling in 1730. So he used the figurate ansatz just for computations to gather data, and, fortunately, he stopped there. Fortunate, because in this data he perceived a special structure which all his forerunners had fail to perceive, and which he probably also would have failed to perceive had he followed the Stirling way till the end, because it it not visible there (as the authors of [2] state it on p.289: “ Bernoulli would probably not have discovered his numbers if he had taken this route.”).

What Jakob Bernoulli perceived and what brought him immortal fame was the following. At each stage $n$ there is just one new rational number $B_n$ joining the game of building $S_n(k)$. If we order the $S_n(k)$ by falling powers, it enters at the very right as the coefficient of the linear term (there is no constant term by definition of the $S_n(k))$. By each next steps this number travels one step to the left to the next higher power and gets multiplied by a well-defined rational number in such a way that it is determined by the lower $B_m$ via the recursion $S_n(k) = 1$. Bernoulli's description of how to build the $S_n(k)$can be seen on pp. 96-97 of loc.cit (unfortunately in latin; an english translation is on pp. 47-48 of [2]).

What Jakob Bernoulli was saying can be rephrased in modern terms as

Theorem The power sum polynomials $S_n(x)$ obey the following recursion scheme $$ \text{$S_n(x) = n\int_0^x S_{n-1}(t) dt + B_n x\quad$ for $n\ge1$} \quad,\quad S_0(x) = x, $$ with the $B_n$ recursively defined by $$ S_n(1) = n\int_0^1 S_{n-1}(t) dt + B_n = 1 \quad,\quad n=0,1,2,\dots $$ How fine this recursion works out can be seen by the following minimalistic MAPLE procedure.

S:=proc(n); if n=0 then x; else T:=n*int(S(n-1),x); B:= 1-eval(T,x=1); T+B*x; end if; end proc;

Corollary The power sum polynomials have the explicit expression $$ S_n(x) = \dfrac{1}{n+1}\sum_{j=0}^{n} \binom{n+1}{j} B_{j} x^{n-j+1} $$ with the $B_n, n=0,1,2,\dots$, called the Bernoulli numbers, recursively given by $$ \sum_{j=0}^{n} \binom{n+1}{j} B_{j} = n+1. $$ For the corollary just note that the linear term of $S_n(x)$ is exactly $B_nx$. Iterating the recursion prescription $k-1$ times yields that the term of degree $k$ of $S_{n+k-1}(x)$ is $$ \dfrac{n+k-1}{k}\cdots\dfrac{n+2}{3}\cdot \dfrac{n+1}{2}B_n x^k = \dfrac{1}{n+k}\binom{n+k}{k}B_nx^k, $$ – where the factors of the numerator stem from the factor in front of the integral, and the factors in the denominator stem from intgrating $x^j$, $j=1,2, \dots, k-1$ – and the claim follows by reindexing. The recursion on the $B_n$ is just a reformulation of the condition $S_n(1) = 1$.

How Jakob Bernoulli arrived at this perception, – or prescription, as you like – remains shrouded in mystery and open to ceaseless speculations, since no single sign of explanation has been handed down to us. What he achieved this way is remarkable: instead of having the computational load of determining all the $S_j(x)$, $j < n$, to obtain $S_n(x)$, this task is now reduced to recursively determining a sequence of rational numbers $B_n$, with the rest of the structure of the $S_n(x)$ clearly determined. And it brings us to our working definition of the Bernoulli numbers $B_n$:

Definition The Bernoulli numbers $B_n, n=0,1,2,\dots$ are defined by $$ \fbox{$\begin{split} B_n :&= \text{coefficient of the linear term of the}\\ \newline &\hspace{1.5em}\text{$n$-th power sum polynomial $S_n(x)$}\\ \newline &= S_n'(0). \end{split}$} $$

Synthesis Our final aim is to bring the definitions of the $A(n,k)$ and the $B_n$ under one roof to produce the formula \begin{equation*} \forall n\ge 2:\quad\sum_{m=1}^{n} (-1)^m \frac{A(n,m)} {\left(n\atop m\right)}=(n+1) B_n.\tag{8} \end{equation*} Remark The notation “$A(n,m)$” in the wikipedia entry for the Eulerian numbers is an unfortunate one, because it conflicts with the standard use as e.g. in [0], where $A(m,n)$ refers to the Eulerian number $\left\langle {n \atop m+1} \right\rangle$ in the Knuth-Karamata notation and the notation is $a(n,m)$ for $ \left\langle {n \atop m} \right\rangle$. The confusion comes about because there are two conventions with regard to the Eulerian polynomials. One convention - to which I adhere - denotes them $A_n(x)$ and have them defined via (2), so they are of degree $n$. The other one denotes them $a_n(x)$ or $S_n(x)$ and have them defined as to have $xa_n(x) = A_n(x)$, so in this convention the $n$-th Eulerian polynomial unfortunately has degree $n-1$, which is confusing and error-prone. The wikipedia entry somehow is vague about the status of the $A_n(x)$. $\hspace{30em} \square$

Now Euler's primary interest in (0) was not to prove such a formula (8), but to put $x:=-1$ in (2) for $n=1,2,\dots$, which would give him $$ -1^n+2^n-3^n+4^n \mp \cdots = \dfrac{A_n(-1)}{2^{n+1}} $$ or $$ \zeta(-n) = 1^n+2^n+3^n+4^n+ \cdots = \dfrac{\sum_k (-1)^k A(n,k)}{(1-2^{n+1})2^{n+1}} \quad, \quad n=1,2, \dots $$ where $$ \zeta(s) := \sum_{k=1}^{\infty} k^{-s} \quad,\quad s \in (1,\infty) \subseteq \mathbb{R} $$ the (real) zeta function, one of Euler's many prestigious brain children. By this method – which later became known as Abel summation – Euler manages “to regularize”, i.e. to give a finite reasonable value to, a divergent expression, here $\zeta(-n)$, some 80 years before Abel. Together with his equally prestigious formulae $$ \zeta(2n) = (-1)^{n+1}\dfrac{(2\pi)^{2n}}{2(2n)!}B_{2n} \quad,\quad n=1,2, \dots $$ this led him to formulate the functional equation of the zeta function and to verify it on the integers with the help of these formulas, which leads down to the equalities $$ \forall n \ge 1:\,\,\dfrac{\sum_k (-1)^k A(n,k)} {(2^{n+1}-1)2^{n+1}} = \dfrac{B_{n+1}}{n+1}, $$ another string of identities between the Eulerian and the Bernoulli numbers (however different from (8)). Since we now know that these cases imply the full functional equation for the full complex zeta function, he conjectured it (for the real case), and, in some sense, implicitely proved it, some hundred years before Riemann, without having notions and tools like analytic continuation at his disposal. For all this see [3].

Nevertheless, (2) is of help also in our situation because of the following

Lemma Let $f(x) = \sum_{k=0}^{\infty} a_k x^k$ be a formal power series. Define the summation series $\Sigma f(x)$ of $f(x)$ as $\Sigma f(x) := \sum_{k=0}^{\infty} (\Sigma a_k) x^k$ with $\Sigma a_k := \sum_{j=0}^k a_j$. Then for a formal power series $g(x) = \sum_{k=0}^{\infty} b_k x^k$ there holds $$ g(x) = \Sigma f(x) \iff g(x) = \dfrac{f(x)}{1-x}. $$ For this just note $\dfrac{f(x)}{1-x} = \sum_{k=0}^{\infty} a_k x^k \sum_{l=0}^{ \infty} x^l$ and multiply following the rules of the Cauchy product.

Then, as a corollary, we obtain

Theorem The generating function of the values of the power sum polynomials at nonnegative integers is given by \begin{equation*}\tag{9} \sum_{k=0}^{\infty} S_n(k) x^k = \dfrac{A_n(x)}{(1-x)^{n+2}} = \sum_{m=0}^n A(n,m) \dfrac{x^m}{(1-x)^{n+2}}. \end{equation*} For this, the summation series of (0) is just $\sum_{k=0}^{\infty} S_n(k) x^k$. Apply the lemma and use (2).

And now our journey has come to an end. The formula (9) will give a closed form for the $S_n(x)$ in terms of a linear combination of certain binomials with coefficients the Eulerian numbers. Taking the coefficient of the linear term then will, in conjunction with our definition of the $B_n$, provide (8). In order not to spoil the fun of doing those computations for oneself: DETAILS ARE LEFT TO THE READER....

—

[0] Comtet, L. – Advanced Combinatorics. D. Reidel 1974.

[1] Edwards, A.W.F. – Pascal's arithmetical triangle. Dover Publications 2019.

[2] Graham, R.L et al. – Concrete Mathematics (2nd Edition). Addison-Wesley 1994.

[3] Euler, L. – Remarques sur un beau rapport entre les séries des puissances tant directes que réciproques. Mémoires de l'académie des sciences de Berlin 17, 1768, pp. 83-106.

[4] Knoebel, A. et al. – Mathematical Masterpieces. Undergraduate Texts in Mathematics. Springer 2007.

[5] Sylla, E.D. – Jacob Bernoulli – The Art of Conjecturing. The Johns Hopkins University Press 2006.

In the references section in the article of wikipedia, an article of Worpitzky is cited. The identity you are looking for is the first (unnumbered) equation in page 222. (One must be careful since Worpitzky uses "old" definitions of the numbers involved.)