André's theorem

Statement

The determination of the number A_n of alternating permutations of the set {1, ..., n} is called André's problem. The numbers A_n are variously known as Euler numbers, zigzag numbers, up/down numbers, or by some combinations of these names. The name Euler numbers in particular is sometimes used for a closely related sequence. The first few values of A_n are 1, 1, 1, 2, 5, 16, 61, 272, 1385, 7936, 50521, ... .

These numbers satisfy a simple recurrence, similar to that of the Catalan numbers: by splitting the set of alternating permutations (both down-up and up-down) of the set { 1, 2, 3, ..., n, n + 1 } according to the position k of the largest entry $n + 1$, one can show that

$$2A_{n+1} = \sum_{k=0}^n \binom{n}{k} A_k A_{n-k}$$

for all $n \ge 1$. (André 1881) used this recurrence to give a differential equation satisfied by the exponential generating function

$$A(x) = \sum_{n=0}^\infty A_n \frac{x^n}{n!}$$

for the sequence $A_{n}$. In fact, the recurrence gives:

$$2\sum_{n\geq 1} A_{n+1} \frac{x^{n+1}}{(n+1)!} = \sum_{n\geq 1} \sum_{k=0}^n \frac{A_k}{k!} \frac{A_{n-k}}{(n-k)!} \frac{x^{n+1}}{n+1} = \int \left(\sum_{k\geq 0}A_k \frac{x^k}{k!}\right) \left(\sum_{j\geq 0}A_j \frac{x^j}{j!}\right) \, dx - x$$

where we substitute $j = n-k$ and $\frac{x^{n+1}}{n+1}=\int x^{k+j}\,dx$. This gives the integral equation

$$2(A(x) - 1 - x) = \int A(x)^2\,dx - x,$$

which after differentiation becomes $2\frac{dA}{dx} - 2 = A^2-1$. This differential equation can be solved by separation of variables (using the initial condition $A(0)=A_0/0!=1$), and simplified using a tangent half-angle formula, giving the final result

$$A(x) = \tan \left(\frac\pi4 + \frac x2\right) = \sec x + \tan x,$$

the sum of the secant and tangent functions. This result is known as André's theorem. A geometric interpretation of this result can be given using a generalization of a theorem by Johann Bernoulli.

It follows from André's theorem that the radius of convergence of the series $A(x)$ is $\pi$/2. This allows one to compute the asymptotic expansion

$$A_n \sim 2 \left(\frac{2}{\pi}\right)^{n + 1} n!\,.$$