23 11
Article 14.2.1
Journal of Integer Sequences, Vol. 17 (2014),
2 3 6 1
47
Asymptotic Expansions of Central Binomial Coefficients and Catalan Numbers
Neven Elezovi´c
Faculty of Electrical Engineering and Computing University of Zagreb
Unska 3 10000 Zagreb
Croatia
[email protected]
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 explana- tion of the nature of the best shift in variablen, 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!≈√ 2πn
n e
n
.
This is the beginning of the following full asymptotic expansions [1, 3], Laplace expansion:
n!∼√ 2πn
n e
n
1 + 1
12n + 1
288n2 − 139
51840n3 − 571
2488320n4 +. . .
(1)
and Stirling series
n!∼√ 2πn
n e
n
exp 1
12n − 1
360n3 + 1
1260n5 +. . .
. (2)
The central binomial coefficient has a well-known asymptotic approximation; see e.g., [3, p. 35]:
2n n
∼ 22n
√nπ
1− 1
8n + 1
128n2 + 5
1024n3 − 21
32768n4 +. . .
. (3)
Luschny [9] gives the following nice expansions:
2n n
∼ 4n pN π/2
2− 2
N2 + 21
N4 − 671
N6 +45081 N8
(4) where N = 8n+ 2, and for the Catalan numbers
1 n+ 1
2n n
∼ 4n−2 M√
M π
128 +160 M2 + 84
M4 +715
M6 − 10180 M8
(5) where M = 4n+ 3. Here, for the sake of the beauty, the exact value 4508034 is replaced by 45081, and 101791316 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 ofn+14 (for the central binomial coefficient) and n+ 34 (for Catalan numbers). In this paper we explain why this happens.
The main subject of this paper is to explain whyN = 8n+ 2 andM = 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
2n n
= Γ(2n+ 1) Γ(n+ 1)2 = 4n
√π ·Γ(n+12)
Γ(n+ 1). (6)
In [6], the following general asymptotic expansion of the quotient of two gamma functions is given:
Γ(x+t)
Γ(x+s) ∼xt−s
∞
X
m=0
Pm(t, s, r)x−m
!1/r
. (7)
Here, s, t and r6= 0 are real numbers. Coefficients Pm =Pm(t, s, r) are polynomials defined by
P0(t, s, r) = 1, (8)
Pm(t, s, r) = r m
m
X
k=1
(−1)k+1Bk+1(t)−Bk+1(s)
k+ 1 Pm−k(t, s, r) (9)
and Bk(t) stands for the Bernoulli polynomials.
In the sequel, we shall use the following properties of Bernoulli polynomials and Bernoulli numbers:
(−1)nBn(−x) = Bn(x) +nxn−1, Bn(1 +x) =Bn(x) +nxn−1, B2n+1 = 0, (n≥1), Bn(0) = (−1)nBn(1) = Bn, Bn(12) =−(1−21−n)Bn,
Bn(−12) =−(1−21−n)Bn+ (−1)n n 2n−1, Bn(14) =−2−n(1−21−n)Bn−n4−nEn−1, Bn(34) = (−1)n+12−n(1−21−n)Bn+n4−nEn−1.
(10)
Denote x=n+α, t= 1/2−α,s = 1−α. Applying (6), we have 2n
n
∼ 22n
√xπ
∞
X
k=0
Pk
xk
!1/r
(11) where sequence (Pn) is defined by P0 = 1 and
Pm= r m
m
X
k=1
Bk+1(12 +α)−Bk+1(α)
k+ 1 Pm−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 ofn. Although natural, this choice usually is not the best one.
2) α= 12: this value leads to easily computable coefficients.
3) 12 −α = 1−(1−α): wherefrom it follows α = 14. Here, the symmetry property of Bernoulli polynomials is used, and this is the best choice for α.
4) 12 −α =−(1−α), i.e., α= 34: 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 α = 16, 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:
2n n
∼ 4n pπ(n+α)
∞
X
m=0
Pm(α)(n+α)−m
!1/r
, (12)
where P0 = 1 and 1. for α= 0
Pm = r m
⌊(m+1)/2⌋
X
k=1
(2−2k−1)B2k
k Pm−2k+1; (13)
2. for α= 14
Pm = r m
⌊m/2⌋
X
k=1
2−2k−1EkPm−2k; (14) 3. for α= 12
Pm = r m
⌊(m+1)/2⌋
X
k=1
(1−2−2k)B2k
k Pm−2k+1; (15)
4. for α= 34
Pm = r m
⌊m/2⌋
X
k=1
2−2k−1(2−Ek)Pm−2k; (16) Proof. Let us write
bk(α) = [Bk+1(12 +α)−Bk+1(α)].
We have
bk(0) =Bk+1(12)−Bk+1.
This value is equal to 0 for even k, and equal to (2−k−2)Bk+1 for odd k, and hence (13) follows.
For α= 14,
bk(14) =Bk+1(14)[(−1)k+1−1]
This is equal to 0 for oddk, and equal to (k+ 1)2−2k−1Ek for even k.
Further,
bk(12) = (−1)k+1[Bk+1(0)−Bk+1(12)]
and (15) follows similarly as in the first case.
Finally,
bk(34) =Bk+1(14)[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−Ek) for even k. Thus (16) follows, completing the proof of the theorem.
It is obvious that the choice α= 14 is superior to others. In fact, the equation Bk+1(1/2−α) =Bk+1(1−α)
is an identity for each oddkonly ifα= 14. 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 Pm(α) for the values of the shiftα observed in Theorem1. Using r = 1 we get:
2n n
∼ 4n
√πn
1− 1
8n + 1
128n2 + 5
1024n3 − 21 32768n4
− 399
262144n5 + 869
4194304n6 +· · ·
, (17)
2n n
∼ 4n q
π(n+14)
1− 1
64 n+ 142 + 21
8192 n+ 144 − 671 524288 n+146
+ 180323
134217728 n+148 − 20898423
8589934592 n+1410 +· · ·
, (18)
2n n
∼ 4n q
π(n+12)
1 + 1
8 n+ 12 + 1
128 n+ 122 − 5 1024 n+ 123
− 21
32768 n+ 124 + 399
262144 n+125 + 869
4194304 n+ 126 +· · ·
, (19)
2n n
∼ 4n qπ(n+34)
1 + 1
4 n+ 34 + 5
64 n+342 + 5 256 n+343
+ 21
8192 n+344 + 21
32768 n+345 + 715
524288 n+ 346 +· · ·
, (20)
3 The role of exponent r
The coefficientsPm(t, s, r) are polynomials in r of degree m, which follows directly from the recursive formula (9).
Theorem 2. Let α= 0. Then
Pm(t, s,−r) = (−1)mPm(t, s, r). (21) Proof. By induction. (21) holds form= 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
2n n
−1
∼
√πn 4n
1 + 1
8n + 1
128n2 − 5
1024n3 − 21 32768n4
+ 399
262144n5 + 869
4194304n6 +· · ·
. (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:
2n n
∼ 22n+1
√πN
4
r 1− 2
N + 2 N2 − 2
N4 − 4
N5 − 12 N6 +. . .
while r= 2 andN = 8n+ 2 gives a good square root analogue of the formula (4):
2n n
∼ 4n+1
√πN r1
2 − 1
N2 + 11
N4 −346
N6 + 22931 N8 +. . ..
4 Catalan numbers
The standard definition of Catalan numbers is given by a recurrence relation, C0 = 1 and Cn+1 =
n
X
k=1
CkCn−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:
Cn= 1 n+ 1
2n n
= Γ(2n+ 1)
Γ(n+ 1)Γ(n+ 2) (23)
Hence, Catalan numbers can be expressed as a ratio of two gamma functions Cn = 4n
√π ·Γ(n+12)
Γ(n+ 2). (24)
Putting x=n+α,t = 12 −α,s = 2−α, from (9) we get Cn ∼ 4n
√πx−3/2
∞
X
m=0
Pmx−m
!1/r
, (25)
with P0 = 1 and
Pm = r m
m
X
k=1
ck(α)Pm−k, (26)
where we denote
ck(α) = Bn+1(α+12)−Bk+1(α−1)
k+ 1 . (27)
As before, 0 and 12 are the natural choice for α. Two other good values follow from α+12 = 1−(α−1) andα+12 =−(α−1), wherefrom one getsα= 34 and α= 14, respectively.
Theorem 3. The following asymptotic expansion holds:
Cn∼ 4n
√π(n+α)−3/2
∞
X
m=0
Pm(α)(n+α)−m
!1/r
, (28)
where P0 = 1 and 1. for α= 0
Pm = r m
m
X
k=1
(2−k−2)Bk+1
k+ 1 + (−1)k
Pm−k; (29)
2. for α= 12
Pm = r m
m
X
k=1
(2−2−k)Bk+1
k+ 1 +(−1)k+1 2k
Pm−k; (30)
3. for α= 34
Pm = r m
⌊m/2⌋
X
k=1
2·4−2k−1(4−E2k)Pm−2k; (31) 4. for α= 14
Pm = r m
m
X
k=1
[2−2k−1Ek+ (−34)k]Pm−k. (32)
Proof. We need to compute explicit coefficients in formula (25).
1) α= 0:
ck(0) = Bk+1(12)−Bk+1(−1) k+ 1
Using (10), we have
ck(0) = −(2−2−k)Bk+1
k+ 1 −(−1)k+1 and (29) follows.
2) α= 12:
ck(12) = Bk+1(1)−Bk+1(−12) k+ 1
Using (10), we have
ck(12) = (2−2−k)Bk+1
k+ 1 +(−1)k 2k . 3) α= 34:
ck(34) = Bk+1(54)−Bk+1(−14) k+ 1
Since
Bk+1(54) =Bk+1(14) + (k+ 1) 1 4k, Bk+1(−14) = (−1)k+1
Bk+1(14) + k+ 1 4k
it follows
ck(34) = 1 + (−1)k k+ 1
Bk+1(14) + k+ 1 4k . Therefore, for odd k we have ck(34) = 0. For even k it follows
ck(34) = 2Bk+1(14) k+ 1 + 2
4k
=−2·4−k−1Ek+ 2·4−k. This proves (31).
4) α= 14:
ck(14) = Bk+1(34)−Bk+1(−34) k+ 1
Since
Bk+1(−34) = (−1)k+1
Bk+1(34) + (k+ 1)(34)k
it follows
ck(54) = 1
k+ 1Bk+1(34)[(−1)k+ 1] + (−1)k(34)k. Therefore, for odd k it holds
ck(14) = (−34)k.
For evenk, after reducing in a similar way as before, we get ck(14) = −2·4−k−1Ek+ (−34)k.
For oddkthis values coincides with previous one, sinceE2n+1 = 0. Hence, (32) is proved.
For the convenience of the reader, here is the short list of the observed coefficients, for r= 1:
Cn ∼ 4n
√πn3
1− 9
8n + 145
128n2 − 1155
1024n3 + 36939 32768n4
− 295911
262144n5 +− 4735445
4194304n6 +· · ·
, (33)
Cn ∼ 4n q
π(n+ 12)3
1− 3
8 n+12 + 25
128 n+122 − 105 1024 n+ 123
+ 1659
32768 n+ 124 − 6237
262144 n+125 + 50765
4194304 n+ 126 +· · ·
. (34)
Cn ∼ 4n qπ(n+ 34)3
1 + 5
64 n+ 342 + 21
8192 n+ 344 + 715 524288 n+346
− 162877
134217728 n+ 348 + 19840275
8589934592 n+3410 +· · ·
. (35)
Cn ∼ 4n q
π(n+ 14)3
1− 3
4 n+14 + 35
64 n+ 142 − 105 256 n+143
+ 2541
8192 n+144 − 7623
32768 n+145 + 90805
524288 n+ 146 +· · ·
. (36) As one can see, the expansion in terms of n+ 34 has additional property that it contains only odd terms.
Corollary 4. The valueα = 34 is the unique value for which asymptotic expansion of Catalan numbers contains only odd terms.
Proof. If this is the case, then coefficientc1(α) from (27) must vanish:
B2(α+ 12)−B2(α−1) = 0.
From this one obtain α= 34.
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− 12) lnx−x+ 12ln(2π) +
∞
X
k=1
(−1)k+1Bk+1(t) k(k+ 1 x−k we immediately get
Γ(x+t)
Γ(x+s) ∼xt−s·exp
∞
X
k=1
Qk(t, s)x−k
!
(37) where Qk(t, s) are polynomials of order k defined by
Qk(t, s) = (−1)k+1Bk+1(t)−Bk+1(s)
k(k+ 1) . (38)
Hence, we obtain:
Theorem 5. The binomial coefficient has the following asymptotic expansions of Stirling’s type:
2n n
∼ 4n
√πnexp ∞
X
k=1
(2−2k−1)B2k
k(2k−1) n−2k+1
(39) 2n
n
∼ 4n q
π(n+ 14) exp
∞
X
k=1
2−4k−2E2k 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.
Cn∼ 4n n√
πnexp ∞
X
k=1
(−1)k+1(2−k−2)Bk+1−k−1 k(k+ 1) n−k
(41)
Cn∼ 4n qπ(n+34)3
exp ∞
X
k=1
2−4k−2(4−E2k)
k (n+ 34)−2k
. (42)
Formulae (39)–(42) are derived in the manuscript [10].
6 The sum of binomial coefficients and Catalan num- bers
In a recent paper, Mattarei [11] proves the following asymptotic expansions:
n
X
k=0
2k k
= 4n+1 3√
πn 1 + 1
24n + 59
384n2 + 2425
9216n3 +O(n−4)
(43)
n
X
k=0
Cn = 4n+1 3n√
πn 1− 5
8n + 475
384n2 + 1225
9216n3 +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:
n
X
k=0
2k k
= 4 3
2n n
m
X
j=0
3−j
(2n−1)(2n/3−1)·(2n/(2j−1)−1) +O(4nn−m−3/2),
n
X
k=0
Cn = 2 3
2n n
m X
j=0
(−3)j + 3−j
(2n−1)(2n/3−1)·(2n/(2j + 1)−1)+O(4nn−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, P0(α) = 1 and a(n)∼ 4n
√π
∞
X
k=0
Pk(α)(n+α)−k−r, (45)
where r >0 is a real number. Then
n
X
k=0
a(k)∼ 4 3 ·4n+1
√π
∞
X
k=0
Sk(α)(n+α)−k−r (46)
where the coefficients of this expansion satisfy S0(α) = 1 and Sk(α) =Pk(α) + 1
3
k−1
X
j=0
(−1)k−j
−j−r k−j
Sj(α) (47)
Proof. Denote Σ(n) =Pn
k=0a(k). Suppose that Σ(n)∼C· 4n
√πn−r+O(n−r−1).
Then
Σ(n)∼a(n) + Σ(n−1)
∼ 4n
√πn−r+C· 4n−1
√π (n−1)−r+O(n−r−1)
∼ 4n
√πn−r+C· 4n−1
√π n−r+O(n−r−1)
∼C· 4n
√πn−r+O(n−r−1)
and from here it follows thatC= 43. 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) = 4n+1 3√
π
∞
X
k=0
Sk(α)(n+α)−k−r. (48)
Then, using the asymptotic expansion (45), we get 4n+1
3√ π
∞
X
k=0
Sk(α)(n+α)−k−r
= 4n
√π
∞
X
k=0
Pk(α)(n+α)−k−r+ 4n 3√ π
∞
X
k=0
Sk(α)(n+α−1)−k−r
= 4n
√π
∞
X
k=0
Pk(α)(n+α)−k−r + 4n
3√ π
∞
X
k=0
Sk(α)(n+α)−k−r
∞
X
j=0
(−1)j
−k−r j
(n+α)−j. Hence
4Sk(α) = 3Pk(α) +
k
X
j=0
(−1)k−j
−j−r k−j
Sj(α).
Extracting from the right side the memberSk, we get (47).
Taking α= 0 andr = 1/2 or r= 3/2, it is easy to obtain the following asymptotics:
n
X
k=0
2k k
∼ 4n+1 3√
πn
1 + 1
24n + 59
384n2 + 2425
9216n3 + 576793 884736n4 + 5000317
2359296n5 + 953111599
113246208n6 +. . .
n
X
k=0
Cn ∼ 4n+1 3n√
πn
1− 5
8n + 475
384n2 + 1225
9216n3 + 395857 98304n4 + 27786605
2359296n5 + 6798801295 113246208n6
.
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 For- mulas, Graphs, and Mathematical Tables, National Bureau of Standards, Applied Math- ematics Series 55, 9th printing, Washington, 1970.
[2] A. Erd´elyi, 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´c and N. Elezovi´c, Bernoulli polynomials and asymptotic expansions of the quotient of gamma functions, J. Comput. Appl. Math. 235 (2011), 3315–3331.
[5] T. Buri´c and N. Elezovi´c, New asymptotic expansions of the gamma function and im- provements of Stirling’s type formulas, J. Comput. Anal. Appl.13 (2011), 785–795.
[6] T. Buri´c and N. Elezovi´c, New asymptotic expansions of the quotient of gamma func- tions, Integral Transform. Spec. Funct. 23 (2012), 355–368.
[7] T. Buri´c, N. Elezovi´c, and R. ˇSimi´c, Asymptotic expansions of the multiple quotients of gamma functions and applications, Math. Inequal. Appl., to appear.
[8] N. Elezovi´c, C. Giordano, and J. Peˇcari´c, The best bounds in Gautschi’s inequality, Math. Inequal. Appl. 3 (2000), 239–252.
[9] P. Luschny, Approximation formulas for the factorial functionn!,
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´elyi, 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 A001163, A001164,A046968, and 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.
