Asymptotic Expansions of Central Binomial Coefficients and Catalan Numbers

Neven Elezović Faculty of Electrical Engineering and Computing University of Zagreb Unska 3 10000 Zagreb Croatia

                   neven.elez@fer.hr

Abstract

We give a systematic view of the asymptotic expansion of two well-known sequences, the central binomial coefficients and the Catalan numbers. The main point is explanation of the nature of the best shift in variable n, in order to obtain “nice” asymptotic expansions. We also give a complete asymptotic expansion of partial sums of these sequences.

1 Introduction

One of the most beautiful formulas in mathematics is the classical Stirling approximation of the factorial function:

n! ≈ \sqrt{2πn}(\frac{n}{e})^{n}.

This is the beginning of the following full asymptotic expansions [1, 3], Laplace expansion:

n! ∼ \sqrt{2πn}(\frac{n}{e})^{n}(1 + \frac{1}{12n} + \frac{1}{288n^{2}} − \frac{139}{51840n^{3}} − \frac{571}{2488320n^{4}} + …)  (1)

and Stirling series

n! ∼ \sqrt{2πn}(\frac{n}{e})^{n} exp(\frac{1}{12n} − \frac{1}{360n^{3}} + \frac{1}{1260n^{5}} + …).  (2)

The central binomial coefficient has a well-known asymptotic approximation; see e.g., [3, p. 35]:

\binom{2n}{n} ∼ \frac{2^{2n}}{\sqrt{nπ}} [1 − \frac{1}{8n} + \frac{1}{128n^{2}} + \frac{5}{1024n^{3}} − \frac{21}{32768n^{4}} + …].  (3)

Luschny [9] gives the following nice expansions:

\binom{2n}{n} ∼ \frac{4^{n}}{\sqrt{Nπ/2}} (2 − \frac{2}{N^{2}} + \frac{21}{N^{4}} − \frac{671}{N^{6}} + \frac{45081}{N^{8}})  (4)

where N = 8n + 2, and for the Catalan numbers

\frac{1}{n + 1}\binom{2n}{n} ∼ \frac{4^{n−2}}{M\sqrt{Mπ}} (128 + \frac{160}{M^{2}} + \frac{84}{M^{4}} + \frac{715}{M^{6}} − \frac{10180}{M^{8}})  (5)

where M = 4n + 3. Here, for the sake of the beauty, the exact value 45080\frac{3}{4} is replaced by 45081, and 10179\frac{13}{16} is replaced by 10180.

We would like to thank the anonymous referee who brought to our attention the existence of the manuscript [10] where similar problems are treated. D. Kessler and J. Schiff proved that expansion mentioned above contains only odd powers of n + \frac{1}{4} (for the central binomial coefficient) and n + \frac{3}{4} (for Catalan numbers). In this paper we explain why this happens.

The main subject of this paper is to explain why N = 8n+2 and M = 4n+3 are the best choices in such expansions, and also to obtain general form of these expansions, especially in the case of the Laplace expansions. In the last section, the asymptotic expansion of the partial sums of binomial coefficients and Catalan numbers are derived, using a simple and efficient recursive algorithm.

2 Central binomial coefficients

Although the central binomial coefficient is expressed as Γ(2n + 1)/Γ(n + 1)^{2}, expansions (1) or (2) cannot be used for direct derivation of (3). Instead, one should use the asymptotic expansion of the ratio of two gamma functions. In the standard reference [3], the connection with generalized Bernoulli polynomials is used. This approach is improved in a series of recent papers [4]–[7]. Namely, from the duplication formula for the gamma function we have

\binom{2n}{n} = \frac{Γ(2n + 1)}{Γ(n + 1)^{2}} = \frac{4^{n}}{\sqrt{π}} · \frac{Γ(n + \frac{1}{2})}{Γ(n + 1)}.  (6)

In [6], the following general asymptotic expansion of the quotient of two gamma functions is given:

\frac{Γ(x + t)}{Γ(x + s)} ∼ x^{t−s} (∑_{m=0}^{∞} P_{m}(t, s, r)x^{−m})^{1/r} .  (7)

Here, s, t and r ≠ 0 are real numbers. Coefficients P_{m} = P_{m}(t, s, r) are polynomials defined by

P_{0}(t, s, r) = 1,  (8)
P_{m}(t, s, r) = \frac{r}{m} ∑_{k=1}^{m}(−1)^{k+1} \frac{B_{k+1}(t) − B_{k+1}(s)}{k + 1}P_{m−k}(t, s, r)  (9)

and B_{k}(t) stands for the Bernoulli polynomials.

In the sequel, we shall use the following properties of Bernoulli polynomials and Bernoulli numbers:

\begin{matrix}(−1)^{n}B_{n}(−x) = B_{n}(x) + nx^{n−1}, \\ B_{n}(1 + x) = B_{n}(x) + nx^{n−1}, \\ B_{2n+1} = 0,  (n ≥ 1), \\ B_{n}(0) = (−1)^{n}B_{n}(1) = B_{n}, \\ B_{n}(\frac{1}{2}) = −(1 − 2^{1−n})B_{n}, \\ B_{n}(−\frac{1}{2}) = −(1 − 2^{1−n})B_{n} + (−1)^{n} \frac{n}{2^{n−1}} , \\ B_{n}(\frac{1}{4}) = −2^{−n}(1 − 2^{1−n})B_{n} − n4^{−n}E_{n−1}, \\ B_{n}(\frac{3}{4}) = (−1)^{n+1}2^{−n}(1 − 2^{1−n})B_{n} + n4^{−n}E_{n−1}. \end{matrix}  (10)

Denote x = n + α, t = 1/2 − α, s = 1 − α. Applying (6), we have

\binom{2n}{n} ∼ \frac{2^{2n}}{\sqrt{xπ}} (∑_{k=0}^{∞} \frac{P_{k}}{x^{k}} )^{1/r}  (11)

where sequence (P_{n}) is defined by P_{0} = 1 and

P_{m} = \frac{r}{m} ∑_{k=1}^{m} \frac{B_{k+1}(\frac{1}{2} + α) − B_{k+1}(α)}{k + 1}P_{m−k}, m ≥ 1.

In order to obtain a useful formula, the parameter α should be chosen in such a way that the values of Bernoulli polynomials can be (easily) calculated. Some simplifications are also possible if these coefficients are connected in a way which reduces complexity of this expression. Therefore, the following choices are indicated:

1) α = 0: this gives “natural” expansion in terms of powers of n. Although natural, this choice usually is not the best one.

2) α = \frac{1}{2}: this value leads to easily computable coefficients.

3) \frac{1}{2} − α = 1 − (1 − α): wherefrom it follows α = \frac{1}{4}. Here, the symmetry property of Bernoulli polynomials is used, and this is the best choice for α.

4) \frac{1}{2} − α = −(1 − α), i.e., α = \frac{3}{4}: This choice will also reduce computation.

The value of the Bernoulli polynomials may be calculated explicitly (in terms of Bernoulli and Euler numbers) for some other constants α, for example α = \frac{1}{6}, but the values will be “complicated” compared to the ones chosen above.

The expansions of the central binomial coefficients are given in the following theorem.

Theorem 1. The following asymptotic expansion is valid:

\binom{2n}{n} ∼ \frac{4^{n}}{\sqrt{π(n + α)}} (∑_{m=0}^{∞} P_{m}(α)(n + α)^{−m})^{1/r} ,  (12)

where P_{0} = 1 and

1. for α = 0

P_{m} = \frac{r}{m} ∑_{k=1}^{⌊(m+1)/2⌋} \frac{(2^{−2k} − 1)B_{2k}}{k} P_{m−2k+1};  (13)

2. for α = \frac{1}{4}

P_{m} = \frac{r}{m} ∑_{k=1}^{⌊m/2⌋} 2^{−2k−1}E_{k}P_{m−2k};  (14)

3. for α = \frac{1}{2}

P_{m} = \frac{r}{m} ∑_{k=1}^{⌊(m+1)/2⌋} \frac{(1 − 2^{−2k})B_{2k}}{k} P_{m−2k+1};  (15)

4. for α = \frac{3}{4}

P_{m} = \frac{r}{m} ∑_{k=1}^{⌊m/2⌋} 2^{−2k−1}(2 − E_{k})P_{m−2k};  (16)

Proof. Let us write

b_{k}(α) = [B_{k+1}(\frac{1}{2} + α) − B_{k+1}(α)].

We have

b_{k}(0) = B_{k+1}(\frac{1}{2}) − B_{k+1}.

This value is equal to 0 for even k, and equal to (2^{−k} − 2)B_{k+1} for odd k, and hence (13) follows.

For α = \frac{1}{4},

b_{k}(\frac{1}{4}) = B_{k+1}(\frac{1}{4})[(−1)^{k+1} − 1]

This is equal to 0 for odd k, and equal to (k + 1)2^{−2k−1}E_{k} for even k.

Further,

b_{k}(\frac{1}{2}) = (−1)^{k+1}[B_{k+1}(0) − B_{k+1}(\frac{1}{2})]

and (15) follows similarly as in the first case.

Finally,

b_{k}(\frac{3}{4}) = B_{k+1}(\frac{1}{4})[1 − (−1)^{k+1}] + (k + 1)4^{−k}

As before, this is equal to 0 for odd k, and equal to (k + 1)2^{−2k−1}(2 − E_{k}) for even k. Thus (16) follows, completing the proof of the theorem.

It is obvious that the choice α = \frac{1}{4} is superior to others. In fact, the equation

B_{k+1}(1/2 − α) = B_{k+1}(1 − α)

is an identity for each odd k only if α = \frac{1}{4}. Hence, this value of α is unique with the property that the asymptotic expansion reduces to even terms.

We shall give the first few terms of asymptotic expansions of P_{m}(α) for the values of the shift α observed in Theorem 1. Using r = 1 we get:

\binom{2n}{n} ∼ \frac{4^{n}}{\sqrt{πn}}[1 − \frac{1}{8n} + \frac{1}{128n^{2}} + \frac{5}{1024n^{3}} − \frac{21}{32768n^{4}}

− \frac{399}{262144n^{5}} + \frac{869}{4194304n^{6}} + ⋯], (17)

\binom{2n}{n} ∼ \frac{4^{n}}{\sqrt{π(n + \frac{1}{4})}}[1 − \frac{1}{64 (n + \frac{1}{4})^{2}} + \frac{21}{8192 (n + \frac{1}{4})^{4}} − \frac{671}{524288 (n + \frac{1}{4})^{6}}

+ \frac{180323}{134217728 (n + \frac{1}{4})^{8}} − \frac{20898423}{8589934592 (n + \frac{1}{4})^{10}} + ⋯], (18)

\binom{2n}{n} ∼ \frac{4^{n}}{\sqrt{π(n + \frac{1}{2})}}[1 + \frac{1}{8 (n + \frac{1}{2})} + \frac{1}{128 (n + \frac{1}{2})^{2}} − \frac{5}{1024 (n + \frac{1}{2})^{3}}

− \frac{21}{32768 (n + \frac{1}{2})^{4}} + \frac{399}{262144 (n + \frac{1}{2})^{5}} + \frac{869}{4194304 (n + \frac{1}{2})^{6}} + ⋯], (19)

\binom{2n}{n} ∼ \frac{4^{n}}{\sqrt{π(n + \frac{3}{4})}}[1 + \frac{1}{4 (n + \frac{3}{4})} + \frac{5}{64 (n + \frac{3}{4})^{2}} + \frac{5}{256 (n + \frac{3}{4})^{3}}

+ \frac{21}{8192 (n + \frac{3}{4})^{4}} + \frac{21}{32768 (n + \frac{3}{4})^{5}} + \frac{715}{524288 (n + \frac{3}{4})^{6}} + ⋯], (20)

3 The role of exponent r

The coefficients P_{m}(t, s, r) are polynomials in r of degree m, which follows directly from the recursive formula (9).

Theorem 2. Let α = 0. Then

P_{m}(t, s, −r) = (−1)^{m}P_{m}(t, s, r).  (21)

Proof. By induction. (21) holds for m = 0 and m = 1. The rest is obvious from (13).

As a corollary, we get that the coefficients of the expansion for r = −1 are identical, up to the sign of odd powers, to the coefficients of the expansion for r = 1. Therefore, from (17) it follows immediately that

\binom{2n}{n}^{−1} ∼ \frac{\sqrt{πn}}{4^{n}}[1 + \frac{1}{8n} + \frac{1}{128n^{2}} − \frac{5}{1024n^{3}} − \frac{21}{32768n^{4}}
+ \frac{399}{262144n^{5}} + \frac{869}{4194304n^{6}} + ⋯].  (22)

Various choices of r may give useful expansions. For example, r = 4 and N = 4n leads to a good approximation with the first two terms:

\binom{2n}{n} ∼ \frac{2^{2n+1}}{\sqrt{πN}} \sqrt[4]{1 − \frac{2}{N} + \frac{2}{N^{2}} − \frac{2}{N^{4}} − \frac{4}{N^{5}} − \frac{12}{N^{6}} + …}

while r = 2 and N = 8n + 2 gives a good square root analogue of the formula (4):

\binom{2n}{n} ∼ \frac{4^{n+1}}{\sqrt{πN}} \sqrt{\frac{1}{2} − \frac{1}{N^{2}} + \frac{11}{N^{4}} − \frac{346}{N^{6}} + \frac{22931}{N^{8}} + …}.

4 Catalan numbers

The standard definition of Catalan numbers is given by a recurrence relation, C_{0} = 1 and

C_{n+1} = ∑_{k=1}^{n} C_{k}C_{n−k}.

Catalan numbers occur in various situations. For instance, Stanley [12, p. 219] explains 66 such situations.

The starting point for us will be the following explicit formula:

C_{n} = \frac{1}{n + 1}\binom{2n}{n} = \frac{Γ(2n + 1)}{Γ(n + 1)Γ(n + 2)}  (23)

Hence, Catalan numbers can be expressed as a ratio of two gamma functions

C_{n} = \frac{4^{n}}{\sqrt{π}} · \frac{Γ(n + \frac{1}{2})}{Γ(n + 2)}.  (24)

Putting x = n + α, t = \frac{1}{2} − α, s = 2 − α, from (9) we get

C_{n} ∼ \frac{4^{n}}{\sqrt{π}} x^{−3/2} (∑_{m=0}^{∞} P_{m}x^{−m})^{1/r} ,  (25)

with P_{0} = 1 and

P_{m} = \frac{r}{m} ∑_{k=1}^{m} c_{k}(α)P_{m−k},  (26)

where we denote

c_{k}(α) = \frac{B_{n+1}(α + \frac{1}{2}) − B_{k+1}(α − 1)}{k + 1}.  (27)

As before, 0 and \frac{1}{2} are the natural choice for α. Two other good values follow from α+ \frac{1}{2} = 1−(α−1) and α+ \frac{1}{2} = −(α−1), wherefrom one gets α = \frac{3}{4} and α = \frac{1}{4}, respectively. Theorem 3. The following asymptotic expansion holds:

C_{n} ∼ \frac{4^{n}}{\sqrt{π}} (n + α)^{−3/2} (∑_{m=0}^{∞} P_{m}(α)(n + α)^{−m})^{1/r} ,  (28)

where P_{0} = 1 and

1. for α = 0

P_{m} = \frac{r}{m} ∑_{k=1}^{m} [\frac{(2^{−k} − 2)B_{k+1}}{k + 1} + (−1)^{k}] P_{m−k};  (29)

2. for α = \frac{1}{2}

P_{m} = \frac{r}{m} ∑_{k=1}^{m} [\frac{(2 − 2^{−k})B_{k+1}}{k + 1} + \frac{(−1)^{k+1}}{2^{k}} ] P_{m−k};  (30)

3. for α = \frac{3}{4}

P_{m} = \frac{r}{m} ∑_{k=1}^{⌊m/2⌋} 2 · 4^{−2k−1}(4 − E_{2k})P_{m−2k};  (31)

4. for α = \frac{1}{4}

P_{m} = \frac{r}{m} ∑_{k=1}^{m}[2^{−2k−1}E_{k} + (−\frac{3}{4})^{k}]P_{m−k}.  (32)

Proof. We need to compute explicit coefficients in formula (25). 1) α = 0:

c_{k}(0) = \frac{B_{k+1}(\frac{1}{2}) − B_{k+1}(−1)}{k + 1}

Using (10), we have

c_{k}(0) = \frac{−(2 − 2^{−k})B_{k+1}}{k + 1} − (−1)^{k+1}

and (29) follows.

2) α = \frac{1}{2}:

c_{k}(\frac{1}{2}) = \frac{B_{k+1}(1) − B_{k+1}(−\frac{1}{2})}{k + 1}

Using (10), we have

c_{k}(\frac{1}{2}) = \frac{(2 − 2^{−k})B_{k+1}}{k + 1} + \frac{(−1)^{k}}{2^{k}} .

3) α = \frac{3}{4}:

c_{k}(\frac{3}{4}) = \frac{B_{k+1}(\frac{5}{4}) − B_{k+1}(−\frac{1}{4})}{k + 1}

Since

B_{k+1}(\frac{5}{4}) = B_{k+1}(\frac{1}{4}) + (k + 1)\frac{1}{4^{k}} ,
B_{k+1}(−\frac{1}{4}) = (−1)^{k+1}[B_{k+1}(\frac{1}{4}) + \frac{k + 1}{4^{k}}]

it follows

c_{k}(\frac{3}{4}) = \frac{1 + (−1)^{k}}{k + 1} [B_{k+1}(\frac{1}{4}) + \frac{k + 1}{4^{k}}.

Therefore, for odd k we have c_{k}(\frac{3}{4}) = 0. For even k it follows

c_{k}(\frac{3}{4}) = \frac{2B_{k+1}(\frac{1}{4})}{k + 1} + \frac{2}{4^{k}}
= −2 · 4^{−k−1}E_{k} + 2 · 4^{−k}.

This proves (31).

4) α = \frac{1}{4}:

c_{k}(\frac{1}{4}) = \frac{B_{k+1}(\frac{3}{4}) − B_{k+1}(−\frac{3}{4})}{k + 1}

Since

B_{k+1}(−\frac{3}{4}) = (−1)^{k+1} [B_{k+1}(\frac{3}{4}) + (k + 1)(\frac{3}{4})^{k}]

it follows

c_{k}(\frac{5}{4}) = \frac{1}{k + 1}B_{k+1}(\frac{3}{4})[(−1)^{k} + 1] + (−1)^{k}(\frac{3}{4})^{k}.

Therefore, for odd k it holds

c_{k}(\frac{1}{4}) = (−\frac{3}{4})^{k}.

For even k, after reducing in a similar way as before, we get

c_{k}(\frac{1}{4}) = −2 · 4^{−k−1}E_{k} + (−\frac{3}{4})^{k}.

For odd k this values coincides with previous one, since E_{2n+1} = 0. Hence, (32) is proved.

For the convenience of the reader, here is the short list of the observed coefficients, for r = 1:

C_{n} ∼ \frac{4^{n}}{\sqrt{πn^{3}}} [1 − \frac{9}{8n} + \frac{145}{128n^{2}} − \frac{1155}{1024n^{3}} + \frac{36939}{32768n^{4}}

− \frac{295911}{262144n^{5}} + −\frac{4735445}{4194304n^{6}} + ⋯], (33)

C_{n} ∼ \frac{4^{n}}{\sqrt{π(n + \frac{1}{2})^{3}}} [1 − \frac{3}{8 (n + \frac{1}{2})} + \frac{25}{128 (n + \frac{1}{2})^{2}} − \frac{105}{1024 (n + \frac{1}{2})^{3}}

+ \frac{1659}{32768 (n + \frac{1}{2})^{4}} − \frac{6237}{262144 (n + \frac{1}{2})^{5}} + \frac{50765}{4194304 (n + \frac{1}{2})^{6}} + ⋯]. (34)

C_{n} ∼ \frac{4^{n}}{\sqrt{π(n + \frac{3}{4})^{3}}} [1 + \frac{5}{64 (n + \frac{3}{4})^{2}} + \frac{21}{8192 (n + \frac{3}{4})^{4}} + \frac{715}{524288 (n + \frac{3}{4})^{6}}

− \frac{162877}{134217728 (n + \frac{3}{4})^{8}} + \frac{19840275}{8589934592 (n + \frac{3}{4})^{10}} + ⋯]. (35)

C_{n} ∼ \frac{4^{n}}{\sqrt{π(n + \frac{1}{4})^{3}}} [1 − \frac{3}{4 (n + \frac{1}{4})} + \frac{35}{64 (n + \frac{1}{4})^{2}} − \frac{105}{256 (n + \frac{1}{4})^{3}}

+ \frac{2541}{8192 (n + \frac{1}{4})^{4}} − \frac{7623}{32768 (n + \frac{1}{4})^{5}} + \frac{90805}{524288 (n + \frac{1}{4})^{6}} + ⋯]. (36)

As one can see, the expansion in terms of n + \frac{3}{4} has additional property that it contains only odd terms.

Corollary 4. The value α = \frac{3}{4} is the unique value for which asymptotic expansion of Catalan numbers contains only odd terms.

Proof. If this is the case, then coefficient c_{1}(α) from (27) must vanish:

B_{2}(α + \frac{1}{2}) − B_{2}(α − 1) = 0.

From this one obtain α = \frac{3}{4}.

5 Expansions of Stirling’s type

Stirling expansion of the factorial function (2) includes the exponential function. Using the known asymptotic expansion

ln Γ(x + t) = (x + t − \frac{1}{2}) ln x − x + \frac{1}{2} ln(2π) + ∑_{k=1}^{∞} \frac{(−1)^{k+1}B_{k+1}(t)}{k(k + 1} x^{−k}

we immediately get

\frac{Γ(x + t)}{Γ(x + s)} ∼ x^{t−s} · exp (∑_{k=1}^{∞} Q_{k}(t, s)x^{−k})  (37)

where Q_{k}(t, s) are polynomials of order k defined by

Q_{k}(t, s) = \frac{(−1)^{k+1}B_{k+1}(t) − B_{k+1}(s)}{k(k + 1)}.  (38)

Hence, we obtain:

Theorem 5. The binomial coefficient has the following asymptotic expansions of Stirling’s type:

\binom{2n}{n} ∼ \frac{4^{n}}{\sqrt{πn}} exp(∑_{k=1}^{∞} \frac{(2^{−2k} − 1)B_{2k}}{k(2k − 1)} n^{−2k+1})  (39)

\binom{2n}{n} ∼ \frac{4^{n}}{\sqrt{π(n + \frac{1}{4})}} exp(∑_{k=1}^{∞} \frac{2^{−4k−2}E_{2k}}{k} n^{−2k}).  (40)

The proof is already carried out in the Theorem 1.

A similar result can be stated for Catalan numbers:

Theorem 6.

C_{n} ∼ \frac{4^{n}}{n\sqrt{πn}} exp(∑_{k=1}^{∞}(−1)^{k+1} \frac{(2^{−k} − 2)B_{k+1} − k − 1}{k(k + 1)}n^{−k})  (41)

C_{n} ∼ \frac{4^{n}}{\sqrt{π(n + \frac{3}{4})^{3}}} exp(∑_{k=1}^{∞} \frac{2^{−4k−2}(4 − E_{2k})}{k}(n + \frac{3}{4})^{−2k}).  (42)

Formulae (39)–(42) are derived in the manuscript [10].

6 The sum of binomial coefficients and Catalan numbers

In a recent paper, Mattarei [11] proves the following asymptotic expansions:

∑_{k=0}^{n} \binom{2k}{k} = \frac{4^{n+1}}{3\sqrt{πn}}(1 + \frac{1}{24n} + \frac{59}{384n^{2}} + \frac{2425}{9216n^{3}} + O(n^{−4}))  (43)

∑_{k=0}^{n} C_{n} = \frac{4^{n+1}}{3n\sqrt{πn}}(1 − \frac{5}{8n} + \frac{475}{384n^{2}} + \frac{1225}{9216n^{3}} + O(n^{−4}))  (44)

The calculation was tedious. For example, it relies on a computer algebra system, since it is based on the following formulas:

∑_{k=0}^{n} \binom{2k}{k} = \frac{4}{3}\binom{2n}{n} ∑_{j=0}^{m} \frac{3^{−j}}{(2n − 1)(2n/3 − 1) · (2n/(2j − 1) − 1)} + O(4^{n}n^{−m−3/2}),

∑_{k=0}^{n} C_{n} = \frac{2}{3}\binom{2n}{n} ∑_{j=0}^{m} \frac{(−3)^{j} + 3^{−j}}{(2n − 1)(2n/3 − 1) · (2n/(2j + 1) − 1)} + O(4^{n}n^{−m−5/2})

The final calculation of the coefficients (43) and (44) was carried out using Maple, with m = 4.

We shall derive an efficient algorithm for recursive calculations of asymptotic expansions of this and similar sums, which enables an easy calculation of the arbitrary coefficient in these expansions.

The theorem will be formulated in such a way that it may be easily applied to both binomial and Catalan sums. It is evident that a similar statement is valid for the asymptotic expansion of the sum of more general functions.

Theorem 7. Suppose that a(n) has the following expansion, P_{0}(α) = 1 and

a(n) ∼ \frac{4^{n}}{\sqrt{π}} ∑_{k=0}^{∞} P_{k}(α)(n + α)^{−k−r},  (45)

where r > 0 is a real number. Then

∑_{k=0}^{n} a(k) ∼ \frac{4}{3} · \frac{4^{n+1}}{\sqrt{π}} ∑_{k=0}^{∞} S_{k}(α)(n + α)^{−k−r}  (46)

where the coefficients of this expansion satisfy S_{0}(α) = 1 and

S_{k}(α) = P_{k}(α) + \frac{1}{3} ∑_{j=0}^{k−1}(−1)^{k−j}\binom{−j − r}{k − j}S_{j}(α)  (47)

Proof. Denote Σ(n) = ∑_{k=0}^{n} a(k). Suppose that

Σ(n) ∼ C · \frac{4^{n}}{\sqrt{π}} n^{−r} + O(n^{−r−1}).

Then

Σ(n) ∼ a(n) + Σ(n − 1)

∼ \frac{4^{n}}{\sqrt{π}} n^{−r} + C · \frac{4^{n−1}}{\sqrt{π}} (n − 1)^{−r} + O(n^{−r−1})

∼ \frac{4^{n}}{\sqrt{π}} n^{−r} + C · \frac{4^{n−1}}{\sqrt{π}} n^{−r} + O(n^{−r−1})

∼ C · \frac{4^{n}}{\sqrt{π}} n^{−r} + O(n^{−r−1})

and from here it follows that C = \frac{4}{3}. The fact that Σ(n) indeed has the asymptotic behavior of this type may be proved in the same way as it is done for the case r = 1/2 in [11].

Hence, we obtain that Σ(n) has the asymptotic expansion of the following form:

Σ(n) = \frac{4^{n+1}}{3\sqrt{π}} ∑_{k=0}^{∞} S_{k}(α)(n + α)^{−k−r}.  (48)

Then, using the asymptotic expansion (45), we get

\frac{4^{n+1}}{3\sqrt{π}} ∑_{k=0}^{∞} S_{k}(α)(n + α)^{−k−r}

= \frac{4^{n}}{\sqrt{π}} ∑_{k=0}^{∞} P_{k}(α)(n + α)^{−k−r} + \frac{4^{n}}{3\sqrt{π}} ∑_{k=0}^{∞} S_{k}(α)(n + α − 1)^{−k−r}

= \frac{4^{n}}{\sqrt{π}} ∑_{k=0}^{∞} P_{k}(α)(n + α)^{−k−r}

+ \frac{4^{n}}{3\sqrt{π}} ∑_{k=0}^{∞} S_{k}(α)(n + α)^{−k−r} ∑_{j=0}^{∞}(−1)^{j}\binom{−k − r}{j}(n + α)^{−j}.

Hence

4S_{k}(α) = 3P_{k}(α) + ∑_{j=0}^{k}(−1)^{k−j}\binom{−j − r}{k − j}S_{j}(α).

Extracting from the right side the member S_{k}, we get (47).

Taking α = 0 and r = 1/2 or r = 3/2, it is easy to obtain the following asymptotics:

∑_{k=0}^{n} \binom{2k}{k} ∼ \frac{4^{n+1}}{3\sqrt{πn}}(1 + \frac{1}{24n} + \frac{59}{384n^{2}} + \frac{2425}{9216n^{3}} + \frac{576793}{884736n^{4}}

+ \frac{5000317}{2359296n^{5}} + \frac{953111599}{113246208n^{6}} + …)

∑_{k=0}^{n} C_{n} ∼ \frac{4^{n+1}}{3n\sqrt{πn}}(1 − \frac{5}{8n} + \frac{475}{384n^{2}} + \frac{1225}{9216n^{3}} + \frac{395857}{98304n^{4}}

+ \frac{27786605}{2359296n^{5}} + \frac{6798801295}{113246208n^{6}} ).

Here, there is no good value of α which would lead to the expansion similar to (18) or (35), as it is evident from the formula (47).

References

[1] M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, National Bureau of Standards, Applied Mathematics Series 55, 9th printing, Washington, 1970.

[2] A. Erdélyi, Asymptotic Expansions, Dover Publications, New York, 1956.

[3] Y. L. Luke, The Special Functions and Their Approximations, Vol. I, Academic Press, New York, 1969.

[4] T. Burić and N. Elezović, Bernoulli polynomials and asymptotic expansions of the quotient of gamma functions, J. Comput. Appl. Math. 235 (2011), 3315–3331.

[5] T. Burić and N. Elezović, New asymptotic expansions of the gamma function and improvements of Stirling’s type formulas, J. Comput. Anal. Appl. 13 (2011), 785–795.

[6] T. Burić and N. Elezović, New asymptotic expansions of the quotient of gamma functions, Integral Transform. Spec. Funct. 23 (2012), 355–368.

[7] T. Burić, N. Elezović, and R. Šimić, Asymptotic expansions of the multiple quotients of gamma functions and applications, Math. Inequal. Appl., to appear.

[8] N. Elezović, C. Giordano, and J. Pečarić, The best bounds in Gautschi’s inequality, Math. Inequal. Appl. 3 (2000), 239–252.

[9] P. Luschny, Approximation formulas for the factorial function n!,

   http://www.luschny.de/math/factorial/approx/SimpleCases.html.

[10] D. Kessler and J. Schiff, The asymptotics of factorials, binomial coefficients and Catalan

    numbers, manuscript, http://u.math.biu.ac.il/~schiff/Papers/prepap3.pdf.

[11] S. Mattarei, Asymptotics of partial sums of central binomial coefficients and Catalan

    numbers, preprint, http://arXiv.math.CO/0906.4290.

[12] Richard P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, 1999.

[13] F. G. Tricomi and A. Erdélyi, The asymptotic expansion of a ratio of Gamma functions, Pacific J. Math., 1 (1951), 133–142.

2010 Mathematics Subject Classification: Primary 11B65; Secondary 41A60, 33B15. Keywords: binomial coefficient; Catalan number; asymptotic expansion; gamma function.

(Concerned with sequences \underline{A001163}, \underline{A001164}, \underline{A046968}, and \underline{A046969}.)

Received March 21 2013; revised versions received June 6 2013; October 14 2013; November 26 2013. Published in Journal of Integer Sequences, January 3 2014.

Return to Journal of Integer Sequences home page.