User:Michael Hardy/proof of André's theorem

The nth Euler number E_n is equal to the number of alternating permutations of the set { 1, 2, 3, ..., n}, i.e. arrangements of that set into a sequence a₁, ..., a_n satisfying

$a_{1}>a_{2}<a_{3}>a_{4}<\cdots .\,$

(There are differing conventions as to how the term "Euler number" is defined, but all are related concepts.) The Euler number is also equal to the number of reverse-alternating permutations, i.e. those that satisfy

$a_{1}<a_{2}>a_{3}<a_{4}>\cdots .\,$

(A bijection between alternating and reverse-alternating permutations is given by

$a_{i}\mapsto n+1-a_{i}.)\,$

The first several Euler numbers are

$E_{0}=1,\quad E_{1}=1,\quad E_{2}=1,\quad E_{3}=2,\quad E_{4}=5,\quad E_{5}=16,\quad E_{6}=61,\quad E_{7}=272,\quad \ldots$

André's theorem states that the exponential generating function of the Euler numbers is

$f(x)=\sum _{n=0}^{\infty }E_{n}{\frac {x^{n}}{n!}}=\sec x+\tan x.$

Here we prove André's theorem by means of a combinatorial argument showing that this generating function satisfies a certain differential equation, and we use the initial condition ƒ(0) = 1. This proof appears is due to André (1881) and also appears in Stanley (1950, pages 46–7). See also this preprint by Stanley.

The principal combinatorial result that we need is this identity:

$2E_{n+1}=\sum _{k=0}^{n}{\binom {n}{k}}E_{k}E_{n-k}{\text{ if }}n\geq 1.\qquad \qquad (1)$

The provision that n ≥ 1 is crucial.

A proof of this combinatorial identity runs as follows. To choose an alternating or reverse-alternating permutation of the set { 1, 2, 3, ..., n, n + 1 }, we

• choose a subset of size k of the set { 1, ..., n }, then
• choose a reverse-alternating permutation a₁, ..., a_k of the set { 1, ..., k }, then
• choose a reverse-alternating permutation b₁, ..., b_n−k of the set { k + 1, ..., n }.

Then the permutation

$a_{k},a_{k-1},a_{k-2},\ldots ,a_{1},n+1,b_{1},b_{2},b_{3},\ldots b_{n-k}\,$

is either alternating or reverse-alternating. The number of ways to choose a permutation of { 1, 2, 3, ..., n, n + 1 } that is either alternating or reverse-alternating is E_n+1, and the number of ways to complete the sequence of steps above is

${\binom {n}{k}}E_{k}E_{n-k}.\,$

This needs to be done for each possible value of k to get a complete list, hence we sum from k = 0 to k = n. This completes the proof of the identity (1).

Multiplication of both sides of (1) by xⁿ⁺¹/(n+1)! and summing over n ≥ 1, and then prepending the constant and first-degree terms, yields

$2f(x)=2E_{0}+2E_{1}x+2\sum _{n=1}^{\infty }E_{n+1}{\frac {x^{n+1}}{(n+1)!}}=2E_{0}+2E_{1}x+\sum _{n=1}^{\infty }\sum _{k=0}^{n}{\binom {n}{k}}E_{k}E_{n-k}{\frac {x^{n+1}}{(n+1)!}}.$

Differentiating both sides, we get

$2f'(x)=2E_{1}+2\sum _{n=1}^{\infty }E_{n+1}{\frac {x^{n}}{n!}}=2E_{1}+\sum _{n=1}^{\infty }\sum _{k=0}^{n}{\binom {n}{k}}E_{k}E_{n-k}{\frac {x^{n}}{n!}}.$

In the last sum, the index n goes from 1 to ∞, not from 0 to ∞. If we change the lower bound of summation from 1 to 0, we simply add 1 to the sum, and compensate by changing the initial term, 2E₁ = 2, to E₁ = 1, getting

$E_{1}+\sum _{n=0}^{\infty }\sum _{k=0}^{n}{\binom {n}{k}}E_{k}E_{n-k}{\frac {x^{n}}{n!}}=1+\sum _{n=0}^{\infty }\sum _{k=0}^{n}\left(E_{k}{\frac {x^{k}}{k!}}\right)\left(E_{n-k}{\frac {x^{n-k}}{(n-k)!}}\right).$

The last sum is over all pairs of positive integers, so the expression above can be rearranged as

$1+\sum _{i=0}^{\infty }\sum _{j=0}^{\infty }E_{i}{\frac {x^{i}}{i!}}\cdot E_{j}{\frac {x^{j}}{j!}}$

(see Cauchy product).

The expression $E_{i}{\frac {x^{i}}{i!}}$ does not change as j goes from 0 to ∞; hence it can be pulled out of the inside sum, getting

$1+\sum _{i=0}^{\infty }\left(E_{i}{\frac {x^{i}}{i!}}\sum _{j=0}^{\infty }E_{j}{\frac {x^{j}}{j!}}\right).$

Now the second sum does not change as i goes from 0 to ∞; hence it can be pulled out of the outer sum, getting

$1+\left(\sum _{j=0}^{\infty }E_{j}{\frac {x^{j}}{j!}}\right)\left(\sum _{i=0}^{\infty }E_{i}{\frac {x^{i}}{i!}}\right).$

This is

$1+(f(x))^{2}.\,$

Consequently we have a differential equation

$2f'(x)=1+(f(x))^{2}.\,$

This can be solved by separation of variables, getting

$f(x)=\tan \left({\frac {x}{2}}+{\text{constant}}\right).$

We have an initial condition ƒ(0) = 1, so we have

$f(x)=\tan \left({\frac {x}{2}}+{\frac {\pi }{4}}\right).$

Finally, a standard tangent half-angle trigonometric identity gives us

$f(x)=\sec x+\tan x.\,$

This completes the proof of André's theorem.

• Stanley, Richard P. (2011). Enumerative Combinatorics, Volume I, second edition. Cambridge University Press..

• André, Désiré (1881), "Sur les permutations alternées", Journal de mathématiques pures et appliquées, 3e série, 7: 167–84