Asymptotic Expansions of P-recursive Sequences

Michael Stoll Mathematisches Institut Universität Bonn Beringstraße 4 D – 53115 Bonn

                    Email: <stoll@rhein.iam.uni-bonn.de>

Bruno Haible Mathematisches Institut II Universität Karlsruhe Kaiserstraße 12 D – 76131 Karlsruhe

             Email: <haible@ma2s2.mathematik.uni-karlsruhe.de>

Started: 4 March 1994 Last change: 5 July 1994

Mathematics Subject Classification: 11B37; 05A15, 05A16, 11B73.

1. Abstract

Many P-recursive sequences admit an asymptotic expansion of the form

f_{n} ∼ K(n)n^{θ}(1 + \frac{a_{1}}{n} + \frac{a_{2}}{n^{2}} + ⋯),

where K(n) is a simple P-recursive leading term. In examples arising in combinatorics, one frequently observes striking integrality properties of the a_{k}: they are rational numbers whose denominators are made up of a finite set of primes only. In this paper we prove this for several examples, by means of an auxiliary P-recursive sequence.

2. Introduction

Recall that a sequence (f_{n}) of complex numbers is called P-recursive if

P_{r}(n)f_{n+r} + ⋯ + P_{0}(n)f_{n} = 0 for all n ≥ 0,

where P_{r}, …, P_{0} ∈ ℂ[n] are polynomials, not all zero. It is well-known (see e.g. [Sta], Theorem 1.5, or [Hai] 1.14) that this is equivalent to the fact that the generating function

f(X) = ∑_{n=0}^{∞} f_{n}X^{n} is D-finite, i.e. satisfies a nontrivial linear differential equation with

coefficients in ℂ[X]. A classical result of Birkhoff and Trjitzinsky (see [Bi], [BiTr], [WiZe] and [Hai] 1.16) describes the asymptotics of the solutions of a recurrence:

Proposition 1: Assume the recurrence relation in the form

P_{r}(n)f_{n+r} + ⋯ + P_{0}(n)f_{n} = 0

with P_{r}, …, P_{0} ∈ ℂ[n], P_{0} ≠ 0, and such that P_{r} has no zero in IN. Then there is a formal fundamental system of r formal asymptotic solutions of the form

a_{n} ∼ exp (μ_{0} · nlog n + μ_{1} · n + μ_{2} · n^{\frac{N−1}{N}} + ⋯ + μ_{N} · n^{\frac{1}{N}} ) ·n^{θ} · ∑_{k=0}^{t} n^{r_{k}/N} · (b_{0k}n^{− \frac{0}{N}} + b_{1k}n^{− \frac{1}{N}} + …) · (log n)^{k}  (1)

with N ∈ IN \ \{0\}, μ_{0} ∈ \frac{1}{N} ℤ, μ_{1}, …, μ_{N} ∈ ℂ, −π ≤ Im μ_{1} < π, θ ∈ ℂ, t ∈ IN, all b_{jk} ∈ ℂ, and b_{0k} = 0 only if b_{0k} = b_{1k} = ⋯ = 0. To each of these r formal asymptotic solutions corresponds an actual solution of the recurrence which has the desired asymptotics. These r solutions form a fundamental system (basis of the solution space) of the recurrence.

3. The main transformation

Let N ∈ IN \ {0} be fixed. We consider generating functions

f(X) = ∑_{n>>−∞} f_{n}X^{n}

such that there is a sequence (a_{k})_{k>>−∞} in ℂ with the property that for all m ∈ ℤ:

f_{n} = ∑_{k<m} a_{k}n^{− \frac{k}{N}} + O(n^{− \frac{m}{N}} ) as n → ∞.

We then say that the sequence (f_{n}) has the asymptotic expansion

f_{n} ∼ ∑_{k} a_{k}n^{− \frac{k}{N}} .

Let F be the vector space of such functions f, and let A = ℂ((T^{\frac{1}{N}})). Theorem 2:

(a) The operator

Φ : \{ \begin{matrix}F & → & A \\ f & ↦ & ∑_{k∈ℤ} a_{k} _{\frac{1}{Γ(\frac{k}{N})}}T^{\frac{k}{N} −1} \end{matrix}\} ,

a linear map which maps every function to its (appropriately encoded) asymptotic development, has the following properties:

(i) f(X) a polynomial ⇒ Φ(f) = 0.

(ii) Φ(Xf′) = \frac{d}{dT} Φ(f).

(iii) Φ(Xf) = e^{T} · Φ(f).

(b) Let σ be the substitution σ : \{ \begin{matrix}ℂ((T^{\frac{1}{N}})) & → & ℂ((X^{\frac{1}{N}})) \\ T & ↦ & log (1 + X) \end{matrix}\} and Ψ := σ ∘ Φ. Then Ψ has the following properties:

(i) f(X) a polynomial ⇒ Ψ(f) = 0.

(ii) Ψ(Xf) = (X + 1) · Ψ(f).

(iii) Ψ(f′) = Ψ(f)′. Proof:

(a) Note that Φ(f) is well-defined because \frac{1}{Γ(α)} is always finite. (i) If f_{n} = 0 for n >> 0 then all a_{k} = 0. (ii) Writing f(X) = ∑_{n} f_{n}X^{n}, we have Xf′(X) = ∑_{n} nf_{n}X^{n}. From

f_{n} = ∑_{k<m+N} a_{k}n^{− \frac{k}{N}} + O(n^{− \frac{m+N}{N}} ) for n → ∞ ∀m ∈ ℤ

Notation: n >> −∞ means n ≥ n_{0} for some n_{0} > −∞. we get

\begin{aligned}nf_{n} & = ∑_{k<m+N} a_{k}n^{− \frac{k}{N} +1} + O(n^{− \frac{m}{N}} ) \\ & = ∑_{k<m} a_{k+N}n^{− \frac{k}{N}} + O(n^{− \frac{m}{N}} ) for n → ∞ ∀m ∈ ℤ. \end{aligned}

Therefore

\begin{aligned}Φ(Xf′(X)) & = ∑_{k} a_{k+N} \frac{1}{Γ(\frac{k}{N} )}T^{\frac{k}{N} −1} = ∑_{k} a_{k} \frac{1}{Γ(\frac{k}{N} − 1)}T^{\frac{k}{N} −2} \\ & = ∑_{k} a_{k} \frac{1}{Γ(\frac{k}{N} )}(\frac{k}{N} − 1)T^{\frac{k}{N} −2} = \frac{d}{dT} Φ(f). \end{aligned}

(iii) Writing f(X) = ∑_{n} f_{n}X^{n}, we have Xf(X) = ∑_{n} f_{n−1}X^{n}, therefore

f_{n−1} = ∑_{j<m} a_{j}(n − 1)^{− \frac{j}{N}} + O((n − 1)^{− \frac{m}{N}} )

= ∑_{j<m} a_{j}n^{− \frac{j}{N}} (1 − \frac{1}{n})^{− \frac{j}{N}} + O(n^{− \frac{m}{N}} )

= ∑_{j<m} a_{j}n^{− \frac{j}{N}} ( ∑_{0≤i< \frac{m−j}{N}} \frac{\frac{j}{N} ⋯ (\frac{j}{N} + i − 1)}{i!} \frac{1}{n^{i}} + O(n^{− \frac{m−j}{N}} )) + O(n^{− \frac{m}{N}} )

= ∑_{{j<m \atop 0≤i< \frac{m−j}{N}}} a_{j} \frac{\frac{j}{N} ⋯ (\frac{j}{N} + i − 1)}{i!}n^{− \frac{j}{N} −i} + O(n^{− \frac{m}{N}} ) ∀m ∈ ℤ.

This implies

Φ(Xf(X)) = ∑_{k} ( ∑_{j+Ni=k} a_{j} \frac{\frac{j}{N} ⋯ (\frac{j}{N} + i − 1)}{i!})\frac{1}{Γ(\frac{k}{N} )}T^{\frac{k}{N} −1}

= ∑_{{i∈IN \atop j∈ℤ}} a_{j} \frac{1}{Γ(\frac{j}{N} )} \frac{1}{i!}T^{\frac{j}{N} +i−1}

= e^{T} · Φ(f).

(b) (i) Follows from (a)(i). (ii) Follows from (a)(iii). (iii) Follows from (a)(ii), using the chain rule:

\begin{aligned}\frac{d}{dX} Ψ(f) & = \frac{d}{dX} σ(Φ(f)) = \frac{1}{1 + X} σ(\frac{d}{dT} Φ(f)) = \frac{1}{1 + X} σ(Φ(Xf′)) \\ & = \frac{1}{1 + X} Ψ(Xf′) = Ψ(f′). \end{aligned}

q.e.d.

Theorem 3:

(a) If f ∈ F is D-finite (i.e. f ∈ D(ℂ[X], ℂ((X^{\frac{1}{N}})))), then a := Φ(f) is D-finite over e^{T} (i.e. a ∈ D(ℂ[e^{T} ], ℂ((T^{\frac{1}{N}})))). In fact, if

P_{s}(X) · (X \frac{d}{dX} )^{s}f(X) + ⋯ + P_{0}(X) · f(X) ∈ ℂ[X]

then

P_{s}(e^{T} ) · (\frac{d}{dT} )^{s}a(T) + ⋯ + P_{0}(e^{T} ) · a(T) = 0.

(b) If f ∈ F is D-finite (i.e. f ∈ D(ℂ[X], ℂ((X^{\frac{1}{N}})))), then a := Φ(f) has the form a(T) = b(e^{T} − 1) where b is D-finite (i.e. b ∈ D(ℂ[X], ℂ((X^{\frac{1}{N}})))). In fact, if

Q_{s}(X) · (\frac{d}{dX} )^{s}f(X) + ⋯ + Q_{0}(X) · f(X) ∈ ℂ[X]

then

Q_{s}(X + 1) · b^{(s)}(X) + ⋯ + Q_{0}(X + 1) · b(X) = 0.

Proof:

(a) Apply Φ and use Theorem 2(a).

(b) Apply Ψ and use Theorem 2(b). q.e.d.

4. Generalized Stirling numbers

We want to transport integrality properties from b(X) to a(T) = b(e^{T} − 1).

If N = 1 and b(X) = ∑_{n=0}^{∞} \frac{b_{n}}{n!} X^{n}, we use the formula ([HalHei] (4.5))

\frac{(e^{T} − 1)^{n}}{n!} = ∑_{k=0}^{∞} S(k, n)\frac{T^{k}}{k!}  (2)

where S(k, n) ∈ IN are the Stirling numbers of the second kind, and get a(T) = ∑_{k=0}^{∞} \frac{a_{k+1}}{k!} T^{k}

with

a_{k+1} = ∑_{n=0}^{k} S(k, n)b_{n}.

Let us generalize this.

Lemma 4: Let N ∈ IN \ \{0\}, M ∈ ℤ, α = \frac{M}{N} ∈ ℚ \ \{−1, −2, −3, …\}. Then

(e^{T} − 1)^{α} = ∑_{n=0}^{∞} s_{n}(α) · \frac{1}{(α + 1) ⋯ (α + n)} · T^{α+n}  (3)

with s_{n}(α) ∈ ℚ and for all primes p:

ord_{p} (s_{n}(α)) ≥ \{ \begin{matrix}0 & if p ∤ N \\ −2n · ord_{p} (N) − ord_{p} ((2n)!) & if p | N \end{matrix} \} .

We emphasize that s_{n}(α) ∈ ℤ_{p} if p ∤ N.

Proof: We may assume that \frac{M}{N} is in lowest terms.

\frac{(e^{T} − 1)^{α}}{T^{α}} = (1 + (\frac{e^{T} − 1}{T} − 1))^{α} = ∑_{m=0}^{∞} \frac{α(α − 1) ⋯ (α − m + 1)}{m!}(\frac{e^{T} − 1}{T} − 1)^{m}

is in ℚ[ ; [T] ; ]. We can therefore define s_{n}(α) by equation (3). Noticing that the terms with

Notation: ord_{p} denotes the p-adic exponential valuation, ord_{p} (x) = sup{n ∈ ℤ : x ∈ p^{n}ℤ_{p}} for x ∈ ℚ_{p}. m > n do not contribute to the coefficient of T^{n}, we get

\frac{s_{n}(α)}{(α + 1) ⋯ (α + n)} = ; \begin{matrix}= ∑_{m=0}^{n} \frac{α(α − 1) ⋯ (α − m + 1)}{m!} · [T^{n}] (\frac{e^{T} − 1}{T} − 1)^{m} \\ = ∑_{m=0}^{n} \frac{α(α − 1) ⋯ (α − m + 1)}{m!} ∑_{k=0}^{m} \binom{m}{k}(−1)^{m−k} · [T^{n}] (\frac{e^{T} − 1}{T})^{k} \\ = ∑_{0≤k≤m≤n} \frac{α(α − 1) ⋯ (α − m + 1)}{m!}\binom{m}{k}(−1)^{m−k}S(n + k, k)\frac{k!}{(n + k)!}, \end{matrix}

that is

s_{n}(α) = ∑_{0≤k≤m≤n} \frac{(α + n) ⋯ (α − m + 1)}{(n + m)!}\binom{n + m}{n + k}(−1)^{m−k}S(n + k, k).

If p ∤ N, then α ∈ ℤ_{p}, and we have ord_{p} ((α + n) ⋯ (α − m + 1)) ≥ ord_{p} ((n + m)!) (this holds for α ∈ ℤ, and throughout ℤ_{p} by p-adic continuity). Therefore s_{n}(α) ∈ ℤ_{p}. If p | N, let e = ord_{p} (N). Then ord_{p} (α + j) = −e for all j ∈ ℤ. Using m ≤ n, we get

ord_{p} (\frac{(α + n) ⋯ (α − m + 1)}{(n + m)!}) = (m + n) · (−e) − ord_{p} ((n + m)!) ≥ −2n · e − ord_{p} ((2n)!)

and finally ord_{p} (s_{n}(α)) ≥ −2n · e − ord_{p} ((2n)!). q.e.d. Corollary 5: Let a(T) and b(X) be as in Theorem 3(b). Assume

Γ(\frac{M}{N} + 1) · b(X) = X^{\frac{M}{N}} · ∑_{n=0}^{∞} b_{n}X^{n}

with b_{n} ∈ ℚ. Then the coefficients ã_{m} = a_{Nm+N+M} of

Γ(\frac{M}{N} + 1) · a(T) = ∑_{m=0}^{∞} ã_{m} \frac{1}{(\frac{M}{N} + 1) ⋯ (\frac{M}{N} + m)}T^{\frac{M}{N} +m}

are ∈ ℚ and satisfy (p being a prime):

(a) If p ∤ N, then

ord_{p} \binom{}{ã_{m}} ≥ min \{ord_{p} (n!b_{n}) : 0 ≤ n ≤ m\}.

If p | N and e := ord_{p} (N), then

ord_{p} \binom{}{ã_{m}} ≥ min \{ord_{p} (b_{n}) − (2m − n)e − ord_{p} ((2(m − n))!) : 0 ≤ n ≤ m\}.

(b) If b_{n} ∈ \frac{1}{n!}ℤ_{p} for all n and p ∤ N, then ã_{m} ∈ ℤ_{p} for all m.

Proof: From b(X) ∈ X^{\frac{M}{N}} ·ℂ[ ; [X] ; ] one gets a(T) ∈ T^{\frac{M}{N}} ·ℂ[ ; [T] ; ], therefore – in the notation of Theorem 2(a) –

a(T) = ∑_{m=0}^{∞} a_{Nm+N+M} \frac{1}{Γ(\frac{M}{N} + m + 1)}T^{\frac{M}{N} +m}.

We write ã_{m} = a_{Nm+N+M} and α = \frac{M}{N}. Substituting Lemma 4 into Γ(α + 1)b(X) = ∑_{n=0}^{∞} b_{n}X^{α+n} gives

Γ(α + 1)a(T) = ∑_{n=0}^{∞} b_{n}∑_{k=0}^{∞} s_{k}(α + n)\frac{1}{(α + n + 1) ⋯ (α + n + k)}T^{α+n+k}.

Taking the coefficient of T^{α+m} here, we get

\frac{Γ(α + 1)}{Γ(α + m + 1)}ã_{m} = ∑_{n+k=m} b_{n}s_{k}(α + n)\frac{1}{(α + n + 1) ⋯ (α + n + k)}

or equivalently

ã_{m} = ∑_{n=0}^{m} b_{n} · s_{m−n}(α + n) · (α + 1) ⋯ (α + n).

(a) If p ∤ N then by Lemma 4 ord_{p} (s_{m−n}(α + n)) ≥ 0, ord_{p} ((α + 1) ⋯ (α + n)) ≥ ord_{p} (n!), and we get ord_{p} \binom{}{ã_{m}} ≥ min \{ord_{p} (n!b_{n}) : 0 ≤ n ≤ m\}. If p | N and e = ord_{p} (N), then by Lemma 4 again ord_{p} (s_{m−n}(α + n)) ≥ −2(m − n)e − ord_{p} ((2(m − n))!), ord_{p} ((α + 1) ⋯ (α + n)) = −ne, and we get ord_{p} \binom{}{ã_{m}} ≥ min \{ord_{p} (b_{n}) − (2m − n)e − ord_{p} ((2(m − n))!) : 0 ≤ n ≤ m\}.

(b) Use (a) and ord_{p} (n!b_{n}) ≥ 0 for all n. q.e.d.

5. Examples

5.1. A multinomial coefficient

Proposition 6: Let r ∈ IN \ \{0\} and K_{r}(n) = \frac{(rn)!}{n!^{r}}. Then K_{r}(n) has the asymptotic expansion

K_{r}(n) ∼ \sqrt{r(2π)^{1−r}} · (r^{r})^{n} · ∑_{k=0}^{∞} ã_{k}n^{−k}

with ã_{0} = 1 and ã_{k} ∈ ℤ[\frac{1}{r}] for all k.

Proof: From Stirling’s formula

n! ∼ (\frac{n}{e})^{n} · \sqrt{2πn} · exp (∑_{k=1}^{∞} \frac{B_{k+1}}{k(k + 1)} \frac{1}{n^{k}} )

we get

K_{r}(n) ∼ r^{rn+ \frac{1}{2}} · (2πn)^{\frac{1−r}{2}} · exp (∑_{k=1}^{∞} \frac{B_{k+1}}{k(k + 1)} \frac{1 − r^{k+1}}{r^{k}} \frac{1}{n^{k}} )

that is

∑_{k=0}^{∞} ã_{k}T^{k} = exp (∑_{k=1}^{∞} \frac{B_{k+1}}{k(k + 1)} \frac{1 − r^{k+1}}{r^{k}} T^{k}).

We have the following

Lemma 7:

If p is a prime and ∑_{k=0}^{∞} \frac{b_{k}}{k!} T^{k} ∈ ℤ_{p}\begin{matrix}[ \\ [ & e^{T} − 1 & ] \\ ] \end{matrix}, then exp (∑_{k=1}^{∞} \frac{b_{k}}{k} T^{k}) ∈ ℤ_{p}[ ; [T] ; ].

Proof: (This is related to Beukers’ lemma.) The maps

\begin{matrix}ℤ_{p}[ ; [X] ; ] & → & ℚ_{p}[ ; [T] ; ] & → & ℚ_{p}[ ; [T] ; ] & → & ℚ_{p}[ ; [T] ; ] \\ F (X) & ↦ & F (e^{T} − 1) = ∑_{k=0}^{∞} \frac{b_{k}}{k!} T^{k} & ↦ & ∑_{k=1}^{∞} \frac{b_{k}}{k} T^{k} & ↦ & exp (∑_{k=1}^{∞} \frac{b_{k}}{k} T^{k}) \end{matrix}

are continuous. We have to prove that the image of the composition map lies in ℤ_{p}[ ; [T] ; ]. Since ℤ_{p}[ ; [T] ; ] is closed and ℤ_{p}[X] is dense in ℤ_{p}[ ; [X] ; ], we have only to prove it for F (X) ∈

ℤ_{p}[X] = ℤ_{p}[1 + X]. Write F (X) = ∑_{i=0}^{m} c_{i}(1 + X)^{i} with c_{i} ∈ ℤ_{p}. Then ∑_{k=0}^{∞} \frac{b_{k}}{k!} T^{k} = ∑_{i=0}^{m} c_{i}e^{iT},

so b_{k} = ∑_{i=0}^{m} c_{i}i^{k}, and

exp (∑_{k=1}^{∞} \frac{b_{k}}{k} T^{k}) = ∏_{i=0}^{m} exp (∑_{k=1}^{∞} \frac{c_{i}i^{k}}{k} T^{k}) = ∏_{i=0}^{m} exp (−c_{i}log (1 − iT)) = ∏_{i=0}^{m} (1 − iT)^{−c_{i}}

= ∏_{i=0}^{m} (∑_{k=0}^{∞} \binom{c_{i} + k − 1}{k}i^{k}T^{k}).

This is in ℤ_{p}[ ; [T] ; ] since \binom{c_{i}+k−1}{k} ∈ ℤ_{p} for every k ∈ IN. q.e.d. Proof:(of proposition 6, continued): Let p be a prime not dividing r. Put c := \frac{1}{r} ∈ ℤ_{p}^{×}. The lemma is applicable to the sequence b_{k} = \frac{B_{k+1}}{k+1} \frac{1−r^{k+1}}{r^{k}} since

\begin{aligned}∑_{k=0}^{∞} \frac{b_{k}}{k!} T^{k} & = ∑_{k=0}^{∞} \frac{B_{k+1}}{(k + 1)!}(\frac{T}{r} )^{k} − r∑_{k=0}^{∞} \frac{B_{k+1}}{(k + 1)!}T^{k} \\ & = (\frac{1}{e^{cT} − 1} − \frac{1}{cT} ) − \frac{1}{c}(\frac{1}{e^{T} − 1} − \frac{1}{T} ) = \frac{1}{e^{cT} − 1} − \frac{1}{c} \frac{1}{e^{T} − 1} = F (e^{T} − 1) \end{aligned}

with F (X) = \frac{1}{(1 + X)^{c} − 1} − \frac{1}{c} \frac{1}{X} = \frac{1}{cX} (\frac{1}{1 + r\binom{c}{2}X + r\binom{c}{3}X^{2} + …} − 1) ∈ ℤ_{p}[ ; [X] ; ]. The

lemma now gives ∑_{k=0}^{∞} ã_{k}T^{k} ∈ ℤ_{p}[ ; [T] ; ]. q.e.d.

5.2. Refinement for r = 2

Proposition 8: K_{2}(n) = \frac{(2n)!}{n!^{2}} has the asymptotic expansion

K_{2}(n) ∼ \frac{4^{n}}{\sqrt{πn}} · ∑_{k=0}^{∞} ã_{k}n^{−k}

with ã_{k} ∈ ℤ[\frac{1}{2}] and ord_{2} \binom{}{ã_{k}} ≥ −3k − ord_{2} (k!) ≥ −4k.

Proof: K_{2}(n) satisfies the recurrence

(n + 1) · K_{2}(n + 1) − 2(2n + 1) · K_{2}(n) = 0 ∀n ∈ IN

In view of Proposition 6, we put f_{n} = \frac{K_{2}(n)}{4^{n}/\sqrt{π}}. The recurrence

(n + 1) · f_{n+1} − (n + \frac{1}{2}) · f_{n} = 0 ∀n ∈ IN

is equivalent to

(X − 1) · f′(X) + \frac{1}{2} · f(X) = 0.

By Theorem 3(b), b(X) satisfies

X · b′(X) + \frac{1}{2} · b(X) = 0.

This implies b(X) = constX^{− \frac{1}{2}} . From f_{n} ∼ n^{− \frac{1}{2}} + O(n^{− \frac{3}{2}} ) one knows a(T) = _{\frac{1}{Γ(\frac{1}{2})}}T^{− \frac{1}{2}} +

O(T^{\frac{1}{2}} ) and b(X) = _{\frac{1}{Γ(\frac{1}{2})}}X^{− \frac{1}{2}} + O(X^{\frac{1}{2}} ). Therefore b(X) = _{\frac{1}{Γ(\frac{1}{2})}}X^{− \frac{1}{2}} . Now apply

Corollary 5 (with \frac{M}{N} = −\frac{1}{2}, b_{0} = 1, b_{n} = 0 for n > 0). We get ord_{p} \binom{}{ã_{k}} ≥ 0 for p ≠ 2 and ord_{2} \binom{}{ã_{k}} ≥ −2k − ord_{2} ((2k)!) = −3k − ord_{2} (k!). Finally use the well-known estimate ord_{p} (k!) ≤ \frac{k}{p−1}. q.e.d.

5.3. Refinement for r = 3

Proposition 9: K_{3}(n) = \frac{(3n)!}{n!^{3}} has the asymptotic expansion

K_{3}(n) ∼ \frac{\sqrt{3}}{2π} \frac{27^{n}}{n} · ∑_{k=0}^{∞} ã_{k}n^{−k}

with ã_{k} ∈ ℤ[\frac{1}{3}] and ord_{3} \binom{}{ã_{k}} ≥ −2k − ord_{3} (k!) ≥ −\frac{5}{2}k.

Proof: K_{3}(n) satisfies the recurrence

(n + 1)^{2} · K_{3}(n + 1) − 3(3n + 1)(3n + 2) · K_{3}(n) = 0 ∀n ∈ IN

In view of Proposition 6, we put f_{n} = _{\frac{K_{3}(n)}{\frac{\sqrt{3}}{2π} 27^{n}}}. The recurrence

(n + 1)^{2} · f_{n+1} − (n + \frac{1}{3})(n + \frac{2}{3}) · f_{n} = 0 ∀n ∈ IN  (4)

is equivalent to

X(X − 1) · f′′(X) + (2X − 1) · f′(X) + \frac{2}{9} · f(X) = 0.  (5)

By Theorem 3(b), b(X) satisfies

X(X + 1) · b′′(X) + (2X + 1) · b′(X) + \frac{2}{9} · b(X) = 0.

Therefore c(X) := b(−X) satisfies

X(X − 1) · c′′(X) + (2X − 1) · c′(X) + \frac{2}{9} · c(X) = 0.  (6)

From f_{n} ∼ \frac{1}{n}(1 + O(\frac{1}{n})) one knows a(T) = 1 + O(T), b(X) = 1 + O(X) and c(X) = 1 + O(X). Observe that (6) is the same differential equation as (5)! Therefore the coefficients c_{n} of c(X) satisfy the recurrence (4) and are determined by c_{0} = 1. We conclude c_{n} = \frac{K_{3}(n)}{27^{n}}, c(X) = ∑_{n=0}^{∞} \frac{K_{3}(n)}{27^{n}}X^{n}, b(X) = ∑_{n=0}^{∞} \frac{K_{3}(n)}{(−27)^{n}} X^{n}. Now apply Corollary 5 (with \frac{M}{N} = 0 and ord_{3} (b_{n}) = −3n + ord_{3} (K_{3}(n)) = −3n + ord_{3} ((3n)!) − 3 ord_{3} (n!) = −2n − 2 ord_{3} (n!)). We get ord_{p} \binom{}{ã_{k}} ≥ 0 for p ≠ 3 and ord_{3} \binom{}{ã_{k}} ≥ min \{−2n − ord_{3} (n!) : 0 ≤ n ≤ k\} = −2k − ord_{3} (k!). q.e.d.

5.4. The number of magic squares

Let H_{n}(r) be the number of n × n matrices with entries in IN and whose row and column sums each equal r. In [Hai] p. 146 it was proved that for fixed r the sequence H_{n}(r) is P-recursive. The recurrence relation for H_{n}(2) is well-known since [ADG]:

H_{n+1}(2) − (n + 1)^{2} · H_{n}(2) + \frac{n^{2}(n + 1)}{2} · H_{n−1}(2) = 0 ∀n ∈ IN

Proposition 10: H_{n}(2) has the asymptotic expansions (a)

H_{n}(2) ∼ \sqrt{e} · \frac{(2n)!}{2^{2n}} · ∑_{k=0}^{∞} a_{k}n^{−k}

with a_{k} ∈ ℤ[\frac{1}{2}], a_{0} = 1 and ord_{2} (a_{k}) ≥ −3k + 1 for k > 0.

(b)

H_{n}(2) ∼ \sqrt{\frac{e}{π}} · \begin{matrix}n! & 2 \\ √ & \overline{n} \end{matrix} · ∑_{k=0}^{∞} ã_{k}n^{−k}

with ã_{k} ∈ ℤ[\frac{1}{2}], ã_{0} = 1 and ord_{2} \binom{}{ã_{k}} ≥ −3k − ord_{2} (k!).

Proof:

(a) It is known ([EvSt]) that

H_{n}(2) ∼ \sqrt{e} · \frac{(2n)!}{2^{2n}}.

We put f_{n} := \frac{H_{n}(2)}{\sqrt{e} · \frac{(2n)!}{2^{2n}}}. The recurrence

(2n + 1)(2n − 1) · f_{n+1} − 2(n + 1)(2n − 1) · f_{n} + 2n · f_{n−1} = 0 ∀n ∈ IN

is equivalent to

4X^{2}(X − 1) · f′′(X) − 2X(X^{2} − 3X − 2) · f′(X) − (2X^{2} + 2X + 3) · f(X) = −3f_{0}.

By Theorem 3(b), b(X) satisfies

4X(X + 1)^{2} · b′′(X) − 2(X + 1)(X^{2} − X − 4) · b′(X) − (2X^{2} + 6X + 7) · b(X) = 0.

We substitute b(X) = (1 + X)^{\frac{1}{2}} exp (\frac{X}{4} ) · c(X). The differential equation for c(X) is simpler:

16X · c′′(X) + 32 · c′(X) − (X + 4) · c(X) = 0.

The coefficients c_{n} of c(X) therefore satisfy the recurrence

c_{n+1} = \frac{4c_{n} + c_{n−1}}{16(n + 1)(n + 2)} ∀n ∈ IN.

From f_{n} ∼ 1 + \frac{1}{4} \frac{1}{n} + O(\frac{1}{n^{2}} ) one knows a(T) = \frac{1}{4} + O(T), b(X) = \frac{1}{4} + O(X),

c(X) = \frac{1}{4} + O(X) and c_{0} = \frac{1}{4}. The closed formula for c_{n}

c_{n} = \frac{1}{⌊\frac{n}{2}⌋!⌊\frac{n+1}{2}⌋!2^{3n+2}}

is now proved by induction, using the identity

(2⌊\frac{n + 1}{2}⌋ + 1) · 2(⌊\frac{n}{2}⌋ + 1) = (n + 1)(n + 2).

This closed formula implies that c_{n} ∈ \frac{1}{2^{3n+2}n!}ℤ. Now b(X) can be written as

b(X) = (∑_{n=0}^{∞} \frac{α_{n}}{2^{n}n!}X^{n})(∑_{n=0}^{∞} \frac{β_{n}}{2^{2n}n!}X^{n})(∑_{n=0}^{∞} \frac{γ_{n}}{2^{3n+2}n!}X^{n})

where α_{n}, β_{n}, γ_{n} are integers. Since lcm {(2^{i}i!)(2^{2j}j!)(2^{3k+2}k!) : i + j + k = n} | 2^{3n+2}n!, the coefficients b_{n} of b(X) satisfy

b_{n} ∈ \frac{1}{2^{3n+2}n!}ℤ.

Now Corollary 5 (with N = 1, M = 0) implies

a_{m+1} ∈ \frac{1}{2^{3m+2}} ℤ.

(b) Combine (a) and Proposition 8, using the fact that lcm {2^{3i} · 2^{3j+ord_{2} (j!)} : i + j = k} |

2^{3k+ord_{2} (k!)}.

q.e.d.

5.5. The number of three-line Young tableaux

Let S_{k}(n) be the number of Young tableaux (see [Kn] p. 61-63) with n entries and at most k rows. In [Hai] p. 166 it was proved that for fixed k the sequence S_{k}(n) is P-recursive, and a recurrence for S_{3}(n) was given:

(n + 3) · S_{3}(n + 1) − (2n + 3) · S_{3}(n) − 3n · S_{3}(n − 1) = 0 ∀n ∈ IN.

Proposition 11: S_{3}(n) has the asymptotic expansion

S_{3}(n) ∼ \sqrt{\frac{27}{4π}} 3^{n}n^{− \frac{3}{2}} · ∑_{k=0}^{∞} ã_{k}n^{−k}

with ã_{k} ∈ ℤ[\frac{1}{2}], ã_{0} = 1 and ord_{2} \binom{}{ã_{k}} ≥ −4k − ord_{2} (k!) ≥ −5k.

Proof: It is known ([Re]) that

S_{3}(n) ∼ \sqrt{\frac{27}{4π}} 3^{n}n^{− \frac{3}{2}} .

We put f_{n} := \frac{S_{3}(n)}{\sqrt{\frac{27}{4π}} 3^{n}}. The recurrence

3(n + 3) · f_{n+1} − (2n + 3) · f_{n} − n · f_{n−1} = 0 ∀n ∈ IN

is equivalent to

X(1 − X)(3 + X) · f′(X) + (6 − 3X − X^{2}) · f(X) = 6f_{0}.

By Theorem 3(b), b(X) satisfies

X(X + 1)(X + 4) · b′(X) + (X^{2} + 5X − 2) · b(X) = 0.

The solution of this differential equation

\frac{b′(X)}{b(X)} = \frac{−X^{2} − 5X + 2}{X(X + 1)(X + 4)} = \frac{1/2}{X} + \frac{−2}{X + 1} + \frac{1/2}{X + 4}

is b(X) = constX^{\frac{1}{2}} (X + 1)^{−2}(X + 4)^{\frac{1}{2}} . From f_{n} ∼ n^{− \frac{3}{2}} + O(n^{− \frac{5}{2}} ) one knows a(T) =

\frac{1}{Γ(\frac{3}{2})}T^{\frac{1}{2}} + O(T^{\frac{3}{2}} ) and b(X) = _{\frac{1}{Γ(\frac{3}{2})}}X^{\frac{1}{2}} + O(X^{\frac{3}{2}} ). Therefore

b(X) = \frac{1}{Γ(\frac{3}{2})}X^{\frac{1}{2}} (1 + X)^{−2}(1 + \frac{X}{4} )^{\frac{1}{2}} .

Now apply Corollary 5 (with N = 2, M = 1). The coefficients b_{n} of (1 + X)^{−2}(1 + \frac{X}{4} )^{\frac{1}{2}} satisfy b_{n} ∈ ℤ_{p} for p ≠ 2 and ord_{2} (b_{n}) = −2n + ord_{2} (\binom{\frac{1}{2}}{n}) = −3n − ord_{2} (n!). Therefore ã_{m} ∈ ℤ_{p} for p ≠ 2 and

ord_{2} \binom{}{ã_{m}} ≥ min \{ord_{2} (b_{n}) − (2m − n) − ord_{2} ((2(m − n))!) : 0 ≤ n ≤ m\}

= min {(−3n − ord_{2} (n!)) − (2m − n) − (m − n) − ord_{2} ((m − n)!) : 0 ≤ n ≤ m}

= min {−3m − n − ord_{2} (n!) − ord_{2} ((m − n)!) : 0 ≤ n ≤ m}
= −4m − ord_{2} (m!).

q.e.d.

5.6. Sums of cubes of binomial coefficients

Let S_{n}(r) = ∑_{k=0}^{n} \binom{n}{k}^{r}. In [Hai] p. 175 it was proved that for fixed r ∈ IN the sequence

S_{n}(r) is P-recursive, and S_{n}(r) ∼ 2^{rn}(\frac{πn}{2})^{\frac{1−r}{2}} \frac{1}{\sqrt{r}}. The recurrence for S_{n}(3) was found by Franel in 1894:

n^{2} · S_{n}(3) − (7n^{2} − 7n + 2) · S_{n−1}(3) − 8(n − 1)^{2} · S_{n−2}(3) = 0 ∀n ∈ IN.  (7)

Proposition 12: S_{n}(3) has the asymptotic expansion

S_{n}(3) ∼ \frac{2^{3n+1}}{\sqrt{3}π} · \frac{1}{n} · ∑_{k=0}^{∞} ã_{k}n^{−k}

with ã_{k} ∈ ℤ[\frac{1}{3}], ã_{0} = 1 and ord_{3} \binom{}{ã_{k}} ≥ −2k + 1 for k > 0. Proof: Since we know that S_{n}(3) ∼ \frac{2^{3n+1}}{\sqrt{3}πn}, we put f_{n} := \frac{S_{n}(3)}{\frac{2^{3n+1}}{\sqrt{3}π}}. The recurrence

8n^{2} · f_{n} − (7n^{2} − 7n + 2) · f_{n−1} − (n − 1)^{2} · f_{n−2} = 0 ∀n ∈ IN

is equivalent to

X(X − 1)(X + 8) · f′′(X) + (3X^{2} + 14X − 8) · f′(X) + (X + 2) · f(X) = 0. By Theorem 3(b), b(X) satisfies

X(X + 1)(X + 9) · b′′(X) + (3X^{2} + 20X + 9) · b′(X) + (X + 3) · b(X) = 0. We first substitute c(X) = b(−9X) ⇔ b(X) = c(−\frac{X}{9} ) and get

X(X − 1)(9X − 1) · c′′(X) + (27X^{2} − 20X + 1) · c′(X) + 3(3X − 1) · c(X) = 0.

We now substitute d(X) = \frac{1}{1+X} c(\frac{X}{1+X} ) ⇔ c(X) = \frac{1}{1−X} d(\frac{X}{1−X} ) and get

X(X + 1)(8X − 1) · d′′(X) + (24X^{2} + 14X − 1) · d′(X) + 2(4X + 1) · d(X) = 0

which is equivalent to

n^{2}d_{n} − (7n^{2} − 7n + 2)d_{n−1} − 8(n − 1)^{2}d_{n−2} = 0.  (8)

From f_{n} ∼ \frac{1}{n}(1 + O(\frac{1}{n})) one knows a(T) = 1+O(T), b(X) = 1+O(X), c(X) = 1+O(X), d(X) = 1 + O(X), d_{0} = 1. Observe that (8) is the same recurrence as (7)! Its solutions are determined by d_{0}. Therefore by induction

d_{n} = S_{n}(3) ∈ IN.

From this we get

c_{n} = ∑_{k=0}^{n} \binom{n}{k}d_{k} ∈ IN

and

b_{n} = (−\frac{1}{9})^{n}c_{n} ∈ ℤ[\frac{1}{3}].

We have d_{n} = S_{n}(3) ≡ S_{n}(1) = 2^{n} (mod 3) for all n and therefore c_{n} ≡ ∑_{k=0}^{n} \binom{n}{k}2^{k} = 3^{n} ≡ 0 (mod 3) for n > 0, that is ord_{3} (b_{n}) ≥ −2n+1 for n > 0. Corollary 5 (with N = 1, M = 1) now shows ã_{m} ∈ ℤ_{p} for p ≠ 3 and ord_{3} \binom{}{ã_{m}} ≥ min \{ord_{3} (b_{n}) : 0 ≤ n ≤ m\} ≥ −2m + 1 for m > 0. q.e.d.

5.7. The Apéry sequence for ζ(2)

Let A_{n} = ∑_{k=0}^{n} \binom{n}{k}^{2}\binom{n + k}{k}. This sequence was used in [Po] to prove that ζ(2) = \frac{π^{2}}{6} is

irrational. It was shown in [Po] that the sequence A_{n} satisfies the recurrence

n^{2} · A_{n} − (11n^{2} − 11n + 3) · A_{n−1} − (n − 1)^{2} · A_{n−2} = 0 ∀n ∈ IN.  (9)

From Stirling’s formula, one has the asymptotic formula (see also [Po] and [Mc])

A_{n} ∼ (\frac{1 + \sqrt{5}}{2})^{5n+4} · \frac{1}{2π\sqrt{5 + 2\sqrt{5}}} · \frac{1}{n}.

Proposition 13: A_{n} has the asymptotic expansion

A_{n} ∼ (\frac{1 + \sqrt{5}}{2})^{5n+4} \frac{1}{2π\sqrt{5 + 2\sqrt{5}}} · \frac{1}{n} · ∑_{k=0}^{∞} ã_{k}n^{−k}

with ã_{k} ∈ \frac{1}{\sqrt{5}^{3k}} ℤ[\frac{1+\sqrt{5}}{2}] ⊂ ℚ(\sqrt{5}) and ã_{0} = 1.

Proof: Put φ := \frac{1+\sqrt{5}}{2}. For later use, we compute φ^{5} = \frac{11 + 5\sqrt{5}}{2} and φ^{−5} = \frac{−11 + 5\sqrt{5}}{2}. Since we know that A_{n} ∼ γφ^{5n} \frac{1}{n} with γ = \frac{φ^{4}}{2π\sqrt{5+2\sqrt{5}}}, we put f_{n} := \frac{A_{n}}{γφ^{5n}}. The recurrence

φ^{5}n^{2} · f_{n} − (11n^{2} − 11n + 3) · f_{n−1} − φ^{−5}(n − 1)^{2} · f_{n−2} = 0 ∀n ∈ IN

is equivalent to

\begin{matrix}X(X − 1)(φ^{−5}X + φ^{5}) · f′′(X) + (3φ^{−5}X^{2} + 22X − φ^{5}) · f′(X) \\ +(φ^{−5}X + 3) · f(X) = 0. \end{matrix}

By Theorem 3(b), b(X) satisfies

\begin{matrix}X(X + 1)(φ^{−5}X + 5\sqrt{5}) · b′′(X) + (3φ^{−5}X^{2} + (−11 + 15\sqrt{5})X + 5\sqrt{5}) · b′(X) \\ +(φ^{−5}X + \frac{−5 + 5\sqrt{5}}{2}) · b(X) = 0. \end{matrix}

We first substitute c(X) = b(−5\sqrt{5}φ^{5}X) ⇔ b(X) = c(−\frac{X}{5\sqrt{5}φ^{5}} ) and get

\begin{matrix}X(X − 1)(−5\sqrt{5}X + φ^{−5}) · c′′(X) + (−15\sqrt{5}X^{2} + (−11 + 15\sqrt{5})X − φ^{−5}) · c′(X) \\ +(−5\sqrt{5}X + \frac{−5 + 5\sqrt{5}}{2}) · c(X) = 0. \end{matrix}

We now substitute d(X) = \frac{1}{1+X} c(\frac{X}{1+X} ) ⇔ c(X) = \frac{1}{1−X} d(\frac{X}{1−X} ) and get X(X + 1)(φ^{5}X − φ^{−5}) · d′′(X) + (3φ^{5}X^{2} + 22X − φ^{−5}) · d′(X) + (φ^{5}X + 3) · d(X) = 0. Next we substitute e(X) = d(φ^{−5}X) ⇔ d(X) = e(φ^{5}X) and get

X(X + φ^{5})(X − φ^{−5}) · e′′(X) + (3X^{2} + 22X − 1) · e′(X) + (X + 3) · e(X) = 0 which is equivalent to

n^{2}e_{n} − (11n^{2} − 11n + 3)e_{n−1} − (n − 1)^{2}e_{n−2} = 0.  (10)

From f_{n} ∼ \frac{1}{n}(1 + O(\frac{1}{n})) one knows a(T) = 1+O(T), b(X) = 1+O(X), c(X) = 1+O(X), d(X) = 1 + O(X), e(X) = 1 + O(X), e_{0} = 1. Observe that (10) is the same recurrence as (9)! Its solutions are determined by e_{0}. Therefore by induction

e_{n} = A_{n} ∈ IN.

From this we get d_{n} = φ^{5n}c_{n} ∈ ℤ[φ],

c_{n} = ∑_{k=0}^{n} \binom{n}{k}d_{k} ∈ ℤ[φ]

and

b_{n} = (−\frac{1}{5\sqrt{5}φ^{5}} )^{n}c_{n} ∈ \frac{1}{\sqrt{5}^{3n}} ℤ[φ].

Since ℤ[φ] is a factorial ring, Corollary 5 can be generalized to hold with ℤ replaced by ℤ[φ] and ℚ replaced by the number field ℚ(\sqrt{5}). Applying it (with N = 1, M = 1), we get ã_{m} ∈ ℚ(\sqrt{5}), ord_{p} \binom{}{ã_{m}} ≥ 0 for all primes p ≠ (\sqrt{5}) of ℚ(\sqrt{5}) and ord(\sqrt{5}) \binom{}{ã_{m}} ≥

min \{ord(\sqrt{5}) (b_{n}) : 0 ≤ n ≤ m\} ≥ −3m. q.e.d.

5.8. The Apéry sequence for ζ(3)

Let A_{n} = ∑_{k=0}^{n} \binom{n}{k}^{2}\binom{n + k}{k}^{2}. This sequence was used in [Po] to prove that ζ(3) is

irrational. It was shown in [Po] that the sequence A_{n} satisfies the recurrence

n^{3} · A_{n} − (34n^{3} − 51n^{2} + 27n − 5) · A_{n−1} + (n − 1)^{3} · A_{n−2} = 0 ∀n ∈ IN.

From Stirling’s formula, one has the asymptotic formula (see also [Po] and [Mc])

A_{n} ∼ (1 + \sqrt{2})^{4n+2} · \frac{1}{(2π\sqrt{2})^{\frac{3}{2}}} · \frac{1}{n^{\frac{3}{2}}} .

Proposition 14: A_{n} has the asymptotic expansion

A_{n} ∼ (1 + \sqrt{2})^{4n+2} · \frac{1}{(2π\sqrt{2})^{\frac{3}{2}}} · \frac{1}{n^{\frac{3}{2}}} · ∑_{k=0}^{∞} ã_{k}n^{−k}

with ã_{k} ∈ ℚ(\sqrt{2}) and ã_{0} = 1. Under the assumption that the sequence (x_{n}) of rational numbers defined by x_{0} = 1 and

\begin{matrix}(n + 1) · x_{n+1} − 2(68n^{2} + 68n + 27) · x_{n} + 6n(772n^{2} + 35) · x_{n−1} \\ −2(2n − 1)^{2}(68n^{2} − 68n + 27) · x_{n−2} + (2n − 1)^{2}(n − 1)(2n − 3)^{2} · x_{n−3} = 0 \end{matrix} (11)

consists of integers, we have ã_{k} ∈ \frac{1}{2^{7k}3^{k}} ℤ[\sqrt{2}].

Proof: Put φ := 1 + \sqrt{2}. For later use, we compute φ^{4} = 17 + 12\sqrt{2} and φ^{−4} = 17 − 12\sqrt{2}. Since we know that A_{n} ∼ γφ^{4n} \frac{1}{n^{\frac{3}{2}}} with γ = _{\frac{1}{(2π\sqrt{2})^{\frac{3}{2}}}} , we put f_{n} := \frac{A_{n}}{γφ^{4n}}. The recurrence

φ^{4}n^{3} · f_{n} − (34n^{3} − 51n^{2} + 27n − 5) · f_{n−1} + φ^{−4}(n − 1)^{3} · f_{n−2} = 0 ∀n ∈ IN

is equivalent to

\begin{matrix}X^{2}(X − 1)(φ^{−4}X − φ^{4}) · f′′′(X) + X(6φ^{−4}X^{2} − 153X + 3φ^{4}) · f′′(X) \\ +(7φ^{−4}X^{2} − 112X + φ^{4}) · f′(X) + (φ^{−4}X − 5) · f(X) = 0. \end{matrix}

By Theorem 3(b), b(X) satisfies X(X + 1)^{2}(φ^{−4}X − 24\sqrt{2}) · b′′′(X)

+(X + 1)(6φ^{−4}X^{2} + (51 − 144\sqrt{2})X − 36\sqrt{2}) · b′′(X)
+(7φ^{−4}X^{2} + (126 − 168\sqrt{2})X + (24 − 72\sqrt{2})) · b′(X)
+(φ^{−4}X + (12 − 12\sqrt{2})) · b(X) = 0.

We first substitute c(X) = b(24\sqrt{2}φ^{4}X) ⇔ b(X) = c(\frac{X}{24\sqrt{2}φ^{4}} ) and get

X(X − 1)(24\sqrt{2}X + φ^{−4})^{2} · c′′′(X)

+(24\sqrt{2}X + φ^{−4})(144\sqrt{2}X^{2} + (51 − 144\sqrt{2})X − \frac{3}{2}φ^{−4}) · c′′(X)

+(8064X^{2} + (−8064 + 3024\sqrt{2})X + (24 − 72\sqrt{2})φ^{−4}) · c′(X) +(1152X + (−576 + 288\sqrt{2})) · c(X) = 0.

We now substitute d(X) = \frac{1}{1+X} c(\frac{X}{1+X} ) ⇔ c(X) = \frac{1}{1−X} d(\frac{X}{1−X} ) and get

X(X + 1)^{2}(φ^{4}X + φ^{−4})^{2} · d′′′(X)

+(X + 1)(φ^{4}X + φ^{−4})((\frac{255}{2} + 90\sqrt{2})X^{2} + 153X + (\frac{51}{2} − 18\sqrt{2})) · d′′(X)

+((6924 + 4896\sqrt{2})X^{3} + (8262 + 5832\sqrt{2})X^{2} + 3816X + (1326 − 936\sqrt{2})) · d′(X) +((1731 + 1224\sqrt{2})X^{2} + (1326 + 936\sqrt{2})X + 171) · d(X) = 0.

Next we substitute e(X) = d(−φ^{−4}X) ⇔ d(X) = e(−φ^{4}X) and get

\begin{matrix}X(X^{2} − 34X + 1)^{2} · e′′′(X) + (X^{2} − 34X + 1)(\frac{15}{2}X^{2} − 153X + \frac{3}{2}) · e′′(X) \\ +(12X^{3} − 486X^{2} + 3816X − 78) · e′(X) + (3X^{2} − 78X + 171) · e(X) = 0. \end{matrix}

From f_{n} ∼ \frac{1}{n^{\frac{3}{2}}} (1 + O(\frac{1}{n})) one knows a(T) = _{\frac{1}{Γ(\frac{3}{2})}}T^{\frac{1}{2}} + O(T^{\frac{3}{2}} ),

b(X) = _{\frac{1}{Γ(\frac{3}{2})}}X^{\frac{1}{2}} + O(X^{\frac{3}{2}} ), c(X) = \frac{\sqrt{24\sqrt{2}φ^{4}}}{Γ(\frac{3}{2})} X^{\frac{1}{2}} + O(X^{\frac{3}{2}} ),

d(X) = \frac{\sqrt{24\sqrt{2}φ^{4}}}{Γ(\frac{3}{2})} X^{\frac{1}{2}} + O(X^{\frac{3}{2}} ), e(X) = \frac{\sqrt{−24\sqrt{2}}}{Γ(\frac{3}{2})}X^{\frac{1}{2}} + O(X^{\frac{3}{2}} ).

We therefore write e(X) = \frac{\sqrt{−24\sqrt{2}}}{Γ(\frac{3}{2})} · ∑_{n=0}^{∞} e_{n}X^{n+ \frac{1}{2}} with e_{0} = 1. The differential equation

for e(X) is equivalent to

(n + 1)(2n + 1)(2n + 3) · e_{n+1}
−2(2n + 1)(68n^{2} + 68n + 27) · e_{n}
+6n(772n^{2} + 35) · e_{n−1}
−2(2n − 1)(68n^{2} − 68n + 27) · e_{n−2}
+(n − 1)(2n − 1)(2n − 3) · e_{n−3} = 0 ∀n ∈ IN.

This already shows that e_{n} ∈ ℚ for all n ∈ IN. If we now put e_{n} = \frac{2^{n}n!}{(2n+1)!} · x_{n}, we see that the sequence (x_{n}) satisfies the recurrence (11). We have assumed – because we cannot prove – that x_{n} ∈ ℤ. We now conclude

e(X) = \frac{\sqrt{−24\sqrt{2}}}{Γ(\frac{3}{2})} · ∑_{n=0}^{∞} e_{n}X^{n+ \frac{1}{2}} with e_{n} ∈ \frac{2^{n}n!}{(2n+1)!}ℤ,

d(X) = \frac{\sqrt{24\sqrt{2}φ^{4}}}{Γ(\frac{3}{2})} · ∑_{n=0}^{∞} d_{n}X^{n+ \frac{1}{2}} with d_{n} = (−φ^{4})^{n}e_{n} ∈ \frac{2^{n}n!}{(2n+1)!}ℤ[\sqrt{2}],

c(X) = \frac{\sqrt{24\sqrt{2}φ^{4}}}{Γ(\frac{3}{2})} · ∑_{n=0}^{∞} c_{n}X^{n+ \frac{1}{2}} with c_{n} = ∑_{k=0}^{n} \binom{n + \frac{1}{2}}{n − k}d_{k} ∈ \frac{n!}{2^{ord^{2} (n!)}(2n + 1)!}ℤ[\sqrt{2}],

b(X) = \frac{1}{Γ(\frac{3}{2})} · ∑_{n=0}^{∞} b_{n}X^{n+ \frac{1}{2}} with b_{n} = \frac{1}{(24\sqrt{2}φ^{4})^{n}} c_{n} ∈ \frac{n!}{2^{ord_{2} (n!)+ \frac{7}{2} n}3^{n}(2n + 1)!}ℤ[\sqrt{2}].

We now apply the formula contained in the proof of Corollary 5 (with N = 2, M = 1):

ã_{m} = ∑_{n=0}^{m} \frac{(2n + 1)!}{2^{2n}n!} · b_{n} · s_{m−n}(n + \frac{1}{2}).

Since ℤ[\sqrt{2}] is a factorial ring, the method of Corollary 5 can be generalized to hold with ℤ replaced by ℤ[\sqrt{2}] and ℚ replaced by the number field ℚ(\sqrt{2}). Using Lemma 4, we get

ord_{p} \binom{}{ã_{m}} ≥ \{ \begin{matrix}−2 ord_{2} (m!) − 11m ≥ −14m & for p = (\sqrt{2}) \\ −m & for p = (3) \\ 0 & for any other prime p \end{matrix} \} q.e.d.

Conjecture 1: The x_{n} defined above are indeed integers. Conjecture 2:

ord_{3} \binom{}{ã_{k}} ≥ 0.

5.9. The number of Baxter permutations

Let B(n) be the number of Baxter permutations, see [CGHK]:

B(n) = \frac{1}{\binom{n+1}{1}\binom{n+1}{2}} · ∑_{k=1}^{n} \binom{n + 1}{k − 1}\binom{n + 1}{k}\binom{n + 1}{k + 1}.

In [Hai] p. 173 we proved the following recurrence:

\begin{matrix}(n + 1)(n + 2) · B(n − 1) − (7n^{2} − 7n − 2) · B(n − 2) \\ −8(n − 2)(n − 3) · B(n − 3) = 0 ∀n ≥ 3 \end{matrix}  (12)

Proposition 15: B(n) has the asymptotic expansion

B(n) ∼ \frac{32}{\sqrt{3}π} \frac{8^{n}}{n^{4}} · ∑_{k=0}^{∞} ã_{k}n^{−k}

with ã_{k} ∈ ℤ[\frac{1}{3}], ã_{0} = 1 and ord_{3} \binom{}{ã_{k}} ≥ −2k.

Proof: From Stirling’s formula it follows that

B(n) ∼ \frac{32}{\sqrt{3}π} \frac{8^{n}}{n^{4}} .

We put f_{n} := \frac{B(n)}{\frac{32}{\sqrt{3}π} 8^{n}}. The recurrence

8(n + 1)(n + 2) · f_{n−1} − (7n^{2} − 7n − 2) · f_{n−2} − (n − 2)(n − 3) · f_{n−3} = 0 ∀n ≥ 3

is equivalent to

\begin{matrix}X^{2}(X + 8)(X − 1) · f′′(X) + 2X(X^{2} + 14X − 24) · f′(X) + 12(X − 4) · f(X) = \\ = (12f_{0} − 96f_{1})X − 48f_{0}. \end{matrix}

By Theorem 3(b), b(X) satisfies

X(X + 1)^{2}(X + 9) · b′′(X) + 2(X + 1)(X^{2} + 16X − 9) · b′(X) + 12(X − 3) · b(X) = 0. We first substitute c(X) = \frac{6}{(−9)^{3}} b(−9X) ⇔ b(X) = \frac{(−9)^{3}}{6} c(−\frac{X}{9} ) and get

\begin{matrix}X(X − 1)(9X − 1)^{2} · c′′(X) + 2(9X − 1)(9X^{2} − 16X − 1) · c′(X) \\ −36(3X + 1) · c(X) = 0. \end{matrix}

Next we substitute d(X) = \frac{1}{1+X} c(\frac{X}{1+X} ) ⇔ c(X) = \frac{1}{1−X} d(\frac{X}{1−X} ) and get

\begin{matrix}X(X + 1)(8X − 1)^{2} · d′′(X) + 2(8X − 1)(24X^{2} + 16X + 1) · d′(X) \\ +2(128X^{2} + 64X + 17) · d(X) = 0. \end{matrix}

We now substitute e(X) = (8X − 1)^{2}d(X) ⇔ d(X) = (8X − 1)^{−2}e(X) and get

X(X + 1)(8X − 1) · e′′(X) + (16X^{2} + 2) · e′(X) − (16X + 2) · e(X) = 0.

Therefore the coefficients e_{n} of e(X) satisfy the recurrence

(n + 1)(n − 2) · e_{n+1} − (7n^{2} − 7n − 2) · e_{n} − 8(n + 1)(n − 2) · e_{n−1} = 0 ∀n ≥ 3 (13)

From f_{n} ∼ \frac{1}{n^{4}} (1 + O(\frac{1}{n})) one knows a(T) = \frac{1}{6}T^{3} + O(T^{4}), b(X) = \frac{1}{6}X^{3} + O(X^{4}), c(X) = X^{3} + O(X^{4}), d(X) = X^{3} + O(X^{4}), e(X) = X^{3} + O(X^{4}), that is e_{0} = 0, e_{1} = 0, e_{2} = 0, e_{3} = 1. Comparing (12) and (13), we see that e′_{n} := \binom{n+1}{4}B(n − 2) also satisfies (13), with the same initial conditions. Therefore by induction

e_{n} = \binom{n + 1}{4}B(n − 2) ∈ IN.

From this we get e(X) ∈ ℤ[ ; [X] ; ], d(X) ∈ ℤ[ ; [X] ; ], c(X) ∈ ℤ[ ; [X] ; ] and

3! · b(X) = X^{3} · ∑_{n=0}^{∞} b_{n}X^{n} with b_{n} ∈ \frac{1}{3^{2n}} ℤ. Corollary 5 (with N = 1, M = 3) now shows

ã_{m} ∈ ℤ_{p} for p ≠ 3 and ord_{3} \binom{}{ã_{m}} ≥ min \{ord_{3} (b_{n}) : 0 ≤ n ≤ m\} ≥ −2m. q.e.d.

5.10. The number of vertices of certain polytopes

Let M_{n} be the number of vertices of the polytope of symmetric doubly stochastic n × n matrices. Put m_{n} := \frac{M_{n}}{n!} . It was proved in [Ka1] and [Hai] p. 163 that the generating function of this sequence is

m(X) = ∑_{n=0}^{∞} m_{n}X^{n} = (\frac{1 + X}{1 − X} )^{1/4}exp (\frac{X}{2} + \frac{X^{2}}{2} ).  (14)

One therefore has the differential equation

P_{1}(X)m′(X) + P_{0}(X)m(X) = 0  (15)

with P_{1}(X) = 2(1 − X^{2}) and P_{0}(X) = −2 − 2X + X^{2} + 2X^{3} which is equivalent to the recurrence

2(n + 1) · m_{n+1} − 2 · m_{n} − 2n · m_{n−1} + m_{n−2} + 2 · m_{n−3} = 0.  (16)

Proposition 16: m_{n} has the asymptotic expansion

m_{n} ∼ n^{− \frac{3}{4}} · c^{(1)} · (ã_{0}^{(1)} + \frac{ã_{1}^{(1)}}{n} + ⋯) + (−1)^{n}n^{− \frac{5}{4}} · c^{(2)} · (ã_{0}^{(2)} + \frac{ã_{1}^{(2)}}{n} + ⋯) (17)

with c^{(1)} = \frac{2^{1/4}e}{Γ(\frac{1}{4})}, c^{(2)} = \frac{2^{−1/4}}{Γ(− \frac{1}{4})},

all ã_{k}^{(j)} ∈ ℤ[\frac{1}{2}], ã_{0}^{(j)} = 1 and ord_{2} (ã_{k}^{(j)}) ≥ −5k − ord_{2} (k!) ≥ −6k.

Proof: Applying the methods of [FlOd1] Prop.6 or [FlOd2] Cor.3 to (14), we get an asymptotic expansion (17) with c^{(1)} = \frac{2^{1/4}e}{Γ(\frac{1}{4})}, c^{(2)} = \frac{2^{−1/4}}{Γ(− \frac{1}{4})} and ã_{0}^{(j)} = 1. By Proposition 1 there

are sequences (m_{n}^{(1)}) and (m_{n}^{(2)}) that satisfy the recurrence (16), have the prescribed asymptotic behaviour

\begin{aligned}m_{n}^{(1)} & ∼ n^{− \frac{3}{4}} · (ã_{0}^{(1)} + \frac{ã_{1}^{(1)}}{n} + ⋯) \\ m_{n}^{(2)} & ∼ (−1)^{n}n^{− \frac{5}{4}} · (ã_{0}^{(2)} + \frac{ã_{1}^{(2)}}{n} + ⋯) \end{aligned}

and together make up m_{n}:

m_{n} = c^{(1)}m_{n}^{(1)} + c^{(2)}m_{n}^{(2)}.

We now examine m_{n}^{(1)} and m_{n}^{(2)} separately. First put f_{n} = m_{n}^{(1)}. By (16), its generating function f(X) satisfies a differential equation P_{1}(X)f′(X) + P_{0}(X)f(X) ∈ ℂ[X]. By Theorem 3(b), b(X) satisfies

P_{1}(X + 1)b′(X) + P_{0}(X + 1)b(X) = 0.

Since this differential equation is linear of order 1, a comparison with (15) yields b(X) = const · m(X + 1). From ã_{0}^{(1)} = 1 one knows a(T) = _{\frac{1}{Γ(\frac{3}{4})}}T^{− \frac{1}{4}} + O(T^{\frac{3}{4}} ) and b(X) =

\frac{1}{Γ(\frac{3}{4})}X^{− \frac{1}{4}} + O(X^{\frac{3}{4}} ). Therefore

b(X) = \frac{1}{Γ(\frac{3}{4})}X^{− \frac{1}{4}} · (1 + \frac{X}{2} )^{1/4}exp (\frac{3}{2}X + \frac{X^{2}}{2} ).

From (1 + \frac{X}{2} )^{1/4} = ∑_{n=0}^{∞} \frac{α_{n}}{2^{3n}n!}X^{n} with α_{n} ∈ ℤ and exp (\frac{3}{2}X + \frac{X^{2}}{2} ) = ∑_{n=0}^{∞} \frac{β_{n}}{2^{n}n!}X^{n}

with β_{n} ∈ ℤ, we infer that we can apply Corollary 5 with N = 4, M = −1, b_{n} ∈ \frac{1}{2^{3n}n!}ℤ.

We get ord_{p} (ã_{m}^{(1)}) ≥ 0 for p ≠ 2 and

ord_{2} (ã_{m}^{(1)}) ≥ min {(−3n − ord_{2} (n!)) − 2(2m − n) − ord_{2} ((2(m − n))!) : 0 ≤ n ≤ m}
= −5m − ord_{2} (m!).

Next put f_{n} = (−1)^{n}m_{n}^{(1)}. By (16), its generating function f(X) satisfies a differential equation P_{1}(−X)f′(X) − P_{0}(−X)f(X) ∈ ℂ[X]. By Theorem 3(b), b(X) satisfies

P_{1}(−X − 1)b′(X) − P_{0}(−X − 1)b(X) = 0.

Since this differential equation is linear of order 1, a comparison with (15) yields b(X) = const · m(−X − 1). From ã_{0}^{(2)} = 1 one knows a(T) = _{\frac{1}{Γ(\frac{5}{4})}}T^{\frac{1}{4}} + O(T^{\frac{5}{4}} ) and b(X) =

\frac{1}{Γ(\frac{5}{4})}X^{\frac{1}{4}} + O(X^{\frac{5}{4}} ). Therefore

b(X) = \frac{1}{Γ(\frac{5}{4})}X^{\frac{1}{4}} · (1 + \frac{X}{2} )^{−1/4}exp (\frac{X}{2} + \frac{X^{2}}{2} ).

From (1 + \frac{X}{2} )^{−1/4} = ∑_{n=0}^{∞} \frac{α_{n}}{2^{3n}n!}X^{n} with α_{n} ∈ ℤ and exp (\frac{X}{2} + \frac{X^{2}}{2} ) = ∑_{n=0}^{∞} \frac{β_{n}}{2^{n}n!}X^{n}

with β_{n} ∈ ℤ, we infer that we can apply Corollary 5 with N = 4, M = 1, b_{n} ∈ \frac{1}{2^{3n}n!}ℤ.

Just as above, we get ord_{p} (ã_{m}^{(2)}) ≥ 0 for p ≠ 2 and ord_{2} (ã_{m}^{(2)}) ≥ −5m − ord_{2} (m!). q.e.d. As another example, let M_{n} be the number of vertices of the polytope of symmetric doubly substochastic n × n matrices. Put m_{n} := \frac{M_{n}}{n!} . It was proved in [Ka2] and [Hai] p. 164 that the generating function of this sequence is

m(X) = ∑_{n=0}^{∞} m_{n}X^{n} = (\frac{1 + X}{1 − X} )^{1/4}exp (\frac{3}{2}X + \frac{X^{2}}{2} ).

One therefore has the differential equation

P_{1}(X)m′(X) + P_{0}(X)m(X) = 0

with P_{1}(X) = 2(1 − X^{2}) and P_{0}(X) = −4 − 2X + 3X^{2} + 2X^{3} which is equivalent to the recurrence

2(n + 1) · m_{n+1} − 4 · m_{n} − 2n · m_{n−1} + 3m_{n−2} + 2 · m_{n−3} = 0.

Proposition 17: m_{n} has the asymptotic expansion

m_{n} ∼ n^{− \frac{3}{4}} · c^{(1)} · (ã_{0}^{(1)} + \frac{ã_{1}^{(1)}}{n} + ⋯) + (−1)^{n}n^{− \frac{5}{4}} · c^{(2)} · (ã_{0}^{(2)} + \frac{ã_{1}^{(2)}}{n} + ⋯)

with c^{(1)} = \frac{2^{1/4}e^{2}}{Γ(\frac{1}{4})} , c^{(2)} = \frac{2^{−1/4}e^{−1}}{Γ(− \frac{1}{4})} ,

all ã_{k}^{(j)} ∈ ℤ[\frac{1}{2}], ã_{0}^{(j)} = 1 and ord_{2} (ã_{k}^{(j)}) ≥ −5k − ord_{2} (k!) ≥ −6k.

Proof: Literally the same as the proof of Proposition 16, except that the equations have to be slightly modified:

b(X) = \frac{1}{Γ(\frac{3}{4})}X^{− \frac{1}{4}} · (1 + \frac{X}{2} )^{1/4}exp (\frac{5}{2}X + \frac{X^{2}}{2} )

and

b(X) = \frac{1}{Γ(\frac{5}{4})}X^{\frac{1}{4}} · (1 + \frac{X}{2} )^{−1/4}exp (−\frac{X}{2} + \frac{X^{2}}{2} ),

respectively. q.e.d.

6. Behind the Examples

We now discuss the examples and the methods used there. Apart from 5.1. all the results were based on the ability to give a closed formula for b(X) or its coefficients b_{n}. In 5.2., 5.5. and 5.10. this was easily done because the differential equation for b(X) was of order 1. In 5.4. we needed some more luck. In 5.3., 5.6., 5.7. and 5.9. it was possible to relate the sequence (b_{n}) to the original sequence and to exploit that the latter was a priori known to assume integral values. Let us explain the genereal idea behind this. If a D-finite function f(X) satisfies a differential equation ∑_{k=0}^{r} p_{k}(X)f^{(k)}(X) = 0 with polynomials p_{k} ∈ ℂ[X] and p_{r}(X) = (X − α_{1}) ⋯ (X − α_{s}), then α_{1}, …, α_{s} (and possibly ∞) are called the singular points of this differential equation or – sloppily – of f. We start from a sequence (F_{n}) in ℤ. Call ρ = lim_{n→∞} F_{n}^{\frac{1}{n}} its growth factor. It is well-known

that \frac{1}{|ρ|} is precisely the convergence radius of its generating function F (X) viewed as a complex analytic function. In other words, \frac{1}{|ρ|} = min \{|α_{j}| : α_{j} ≠ 0\}. We then put f_{n} = \frac{F_{n}}{γ_{0}ρ^{n}} with some constant γ_{0} ≠ 0. Its generating function is simply

f(X) = \frac{1}{γ_{0}} F (\frac{X}{ρ} ). Its singular points are ρα_{1}, …, ρα_{s}, ∞. Since lim_{n→∞} f_{n}^{\frac{1}{n}} = 1, 1 is among them. By Theorem 3(b), the singular points of b(X) are ρα_{1} − 1, …, ρα_{s} − 1, ∞, and 0 is among them. We now use a couple of linear fractional (Möbius) transformations to map these singular points onto those of f or F. These Möbius transformations must of course map 0 to 0 since we are handling power series developed around 0 and want to get information about its coefficients. Example 5.3. went like this: Start with a recurrence

(n + 1) (αn + β)f_{n+1} − (αn^{2} + (2β − α)n + γ)f_{n} = 0 ∀n ∈ IN  (∗)

with α, β, γ ∈ ℂ, α ≠ 0, γ ≠ 0, −\frac{β}{α} ∉ IN. (Example 5.3. was the special case α = 1, β = 1, γ = \frac{2}{9}.) This is equivalent to

αX(X − 1) · f′′(X) + β(2X − 1) · f′(X) + γ · f(X) = 0.

These are the singular points:

\begin{matrix}f(X) & 0 & 1 & ∞ \\ b(X) & −1 & 0 & ∞ \\ c(X) & 1 & 0 & ∞ \end{matrix}

To achieve this, we simply set c(X) := b(−X). The differential equations for b(X) and c(X):

αX(X + 1) · b′′(X) + β(2X + 1) · b′(X) + γ · b(X) = 0,
αX(X − 1) · c′′(X) + β(2X − 1) · c′(X) + γ · c(X) = 0.

Assuming that c(X) ∈ ℂ[ ; [X] ; ], the coefficients of c(X) satisfy the same recurrence relation (∗) and are thus determined by the first coefficient. We conclude that c(X) and f(X) are linearly dependent. Examples 5.6. and 5.7. went like this: Start with a recurrence

αn^{2}F_{n} + (β(n − \frac{1}{2})^{2} + β′)F_{n−1} + γ(n − 1)^{2}F_{n−2} = 0 ∀n ∈ ℤ  (∗)

with α, β, β′, γ ∈ ℂ, α ≠ 0, γ ≠ 0, β^{2} − 4αγ > 0. (Example 5.6. was the special case α = 1, β = −7, β′ = −\frac{1}{4}, γ = −8, and Example 5.7. was the special case α = 1, β = −11, β′ = −\frac{1}{4}, γ = −1.) This is equivalent to

X(α + βX + γX^{2}) · F′′(X) + (α + 2βX + 3γX^{2}) · F′(X) + (\frac{β}{4} + β′ + γX) · F (X) = 0.

Let φ be the solution of the quadratic equation αx^{2} + βx + γ = 0 with largest absolute value. The growth factor of F is ρ = φ. We therefore substitute F (X) = γ_{0}f(φX) ⇔ f(X) = \frac{1}{γ_{0}} F (\frac{X}{φ} ). These are the singular points:

\begin{matrix}F (X) & 0 & \frac{1}{φ} & \frac{αφ}{γ} & ∞ \\ f(X) & 0 & 1 & \frac{αφ^{2}}{γ} & ∞ \\ b(X) & −1 & 0 & \frac{αφ^{2}}{γ} − 1 & ∞ \end{matrix}

We are looking for a Möbius transformation that maps the singular points of b(X) to the singular points of F (X), mapping 0 to 0. This is indeed possible since they have the same cross ratio: λ(−1, 0, \frac{αφ^{2}}{γ} − 1, ∞) = λ(\frac{1}{φ}, 0, ∞, \frac{αφ}{γ}). We write this Möbius transformation as composition of three elementary substitutions:

c(X) = b((\frac{αφ^{2}}{γ} − 1)X) ⇔ b(X) = c( \frac{X}{\frac{αφ^{2}}{γ} − 1})

d(X) = \frac{1}{1 + X} c(\frac{X}{1 + X} ) ⇔ c(X) = \frac{1}{1 − X} d(\frac{X}{1 − X} )

e(X) = d(−\frac{γ}{αφ}X) ⇔ d(X) = e(−\frac{αφ}{γ}X)

The singular points are transformed like this:

\begin{matrix}b(X) & −1 & 0 & \frac{αφ^{2}}{γ} − 1 & ∞ \\ c(X) & −_{\frac{1}{\frac{αφ^{2}}{γ} −1}} & 0 & 1 & ∞ \\ d(X) & −\frac{γ}{αφ^{2}} & 0 & ∞ & −1 \\ e(X) & \frac{1}{φ} & 0 & ∞ & \frac{αφ}{γ} \end{matrix}

We then expect to find some relation between e(X) and F (X). In fact, after a long and tedious computation – better done with Maple V than by hand – one gets

X(α + βX + γX^{2}) · e′′(X) + (α + 2βX + 3γX^{2}) · e′(X) + (\frac{β}{4} + β′ + γX) · e(X) = 0.

Assuming that e(X) ∈ ℂ[ ; [X] ; ], the coefficients of e(X) satisfy the same recurrence relation (∗) and are thus determined by the first coefficient. We conclude that e(X) and F (X) are linearly dependent. Example 5.9. was done similarly, with the only modification that the singular points don’t all have multiplicity one. Example 5.8. was done similarly: Start with a recurrence

αn^{3}F_{n} + (β(n − \frac{1}{2})^{3} + β′(n − \frac{1}{2}))F_{n−1} + γ(n − 1)^{3}F_{n−2} = 0 ∀n ∈ ℤ

with α, β, β′, γ ∈ ℂ, α ≠ 0, γ ≠ 0, β^{2} − 4αγ > 0. (Example 5.8. was the special case α = 1, β = −34, β′ = −\frac{3}{2}, γ = 1.) This is equivalent to

\begin{matrix}X^{2}(α + βX + γX^{2}) · F′′′(X) + X(3α + \frac{9}{2}βX + 6γX^{2}) · F′′(X) \\ +(α + (\frac{13}{4}β + β′)X + 7γX^{2}) · F′(X) + (\frac{β}{8} + \frac{β′}{2} + γX) · F (X) = 0. \end{matrix}

We make the same substitutions as above, getting f(X), b(X), c(X), d(X), e(X). After a very long computation, one gets the following differential equation for e(X):

X(α + βX + γX^{2})^{2} · e′′′(X) + \frac{3}{2}(α + βX + γX^{2})(α + 3βX + 5γX^{2}) · e′′(X)

+(α(\frac{9}{4}β + β′) + (ββ′ + \frac{13}{4}β^{2} + 8αγ)X + γ(\frac{57}{4}β + β′)X^{2} + 12γ^{2}X^{3}) · e′(X)

+((\frac{1}{8}β^{2} + \frac{1}{2}ββ′ + αγ) + γ(\frac{9}{4}β + β′)X + 3γ^{2}X^{2}) · e(X) = 0.

Writing e(X) = γ_{1}∑_{n=0}^{∞} e_{n}X^{n+ \frac{1}{2}} with some constant γ_{1} ≠ 0, this is equivalent to the recur-

rence α^{2}(n + 1)(2n + 1)(2n + 3) · e_{n+1}

+α(2n + 1)(β((2n + 1)^{2} + \frac{1}{2}) + 2β′) · e_{n}

+2n(αγ(4n^{2} + 3) + 2β^{2}n^{2} + 2ββ′) · e_{n−1}

+γ(2n − 1)(β((2n − 1)^{2} + \frac{1}{2}) + 2β′) · e_{n−2}

+γ^{2}(n − 1)(2n − 1)(2n − 3) · e_{n−3} = 0 ∀n ∈ IN.

It is not clear to us how this sequence (e_{n}) is related to (F_{n}).

7. References

[ADG] Harsh Anand, Vishwa Chander Dumir, Hansraj Gupta: A combinatorial distribution problem. Duke Math. J. 33 (1966), 757-769.

[Bi] George D. Birkhoff: Formal theory of irregular difference equations.

Acta Math. 54 (1930), 205-246.

[BiTr] George D. Birkhoff, W. J. Trjitzinsky: Analytic theory of singular difference equations.

Acta Math. 60 (1932), 1-89.

[CGHK] Fan R. K. Chung, Ronald L. Graham, V. E. Hogatt Jr., M. Kleiman: The number of Baxter permutations. J. Combinatorial Theory (A) 24 (1978), 382-394.

[EvSt] C. J. Everett, P. R. Stein: The asymptotic number of integer stochastic matrices. Discrete Math. 1 (1971), 55-72.

[FlOd1] Philippe Flajolet, Andrew Odlyzko: The average height of binary trees and other simple trees. Journal of Computer and System Sciences 25 (1982), 171-213.

[FlOd2] Philippe Flajolet, Andrew Odlyzko: Singularity analysis of generating functions.

SIAM J. Discrete Math. 3 (1990), 216-240.

[Hai] Bruno Haible: D-finite Potenzreihen in mehreren Variablen.

Diplomarbeit, Universität Karlsruhe, June 1989.

[HalHei] Heinz-Richard Halder, Werner Heise: Einführung in die Kombinatorik.

Carl Hanser Verlag. München, Wien 1976.

[Ka1] M. Katz: On the extreme points of a certain convex polytope.

J. Combinatorial Theory 8 (1970), 417-423.

[Ka2] M. Katz: On the extreme points of the set of substochastic and symmetric matrices. J. Math. Anal. Appl. 37 (1972), 576-579.

[Kn] Donald E. Knuth: The Art of Computer Programming. Vol. 3: Sorting and Searching. Addison-Wesley, Reading, Mass. 1968.

[Mc] Richard J. McIntosh: An asymptotic formula for binomial sums. Preprint.

[Po] Alfred van der Poorten: A proof that Euler missed ..., Apéry’s proof of the irrationality of ζ(3). Math. Intelligencer 1 (1979), 195-203.

[Re] Amitai Regev: Asymptotic values for degrees associated with strips of Young diagrams. Advances in Math. 41 (1981), 115-136.

[Sta] Richard P. Stanley: Differentiably finite power series.

European J. Combin. 1 (1980), 175-188. MR # 81m:05012.

[WiZe] Jet Wimp, Doron Zeilberger: Resurrecting the asymptotics of linear recurrences. Journal of Mathematical Analysis and Applications 111 (1985), 162-176. MR # 87b:05015.