A set of approximations the central binomial coefficient
sa...@kt-algorithms.com
coefficient is of the form:
C(2n, n) ~= 4^n / sqrt( Rm(n) )
Rm being a rational function of max. degree m+1 (m>0):
Rm(n) = (pi n^(m+1) + sum(i=0,m) Pi n^i) / (n^m + sum(i=0,m-1) Qi
n^i)
and where the 2m+1 coefficients are defined by simply requiring exact
results for 2m>=n>=0; note that C(0,0)=1 implies that Q0=P0.
Example: m=1
------------
C(2n, n) ~= 4^n / sqrt( (pi n^2 + P1 n + P0)/ (n + Q0) )
P1 = 53 pi - 164
P0 = 18 pi - 56
Q0 = P0
with a |rel. error| < 5.0*10^-5 for n>=0.
Error profile:
n rel. error n rel. error
----------------------------------------
0 0 12 4.023*10^-5
1 0 13 3.845*10^-5
2 0 14 3.678*10^-5
3 2.923*10^-5 15 3.521*10^-5
4 4.312*10^-5 16 3.375*10^-5
5 4.850*10^-5 17 3.239*10^-5
6 4.983*10^-5 18 3.112*10^-5
7 4.927*10^-5 19 2.994*10^-5
8 4.782*10^-5 20 2.884*10^-5
9 4.600*10^-5 30 2.096*10^-5
10 4.406*10^-5 40 1.641*10^-5
11 4.211*10^-5 50 1.346*10^-5
Example: m=2
------------
C(2n, n) ~= 4^n / sqrt( (pi n^3 + P2 n^2 + P1 n + P0)/ (n^2 + Q1
n + Q0) )
P2 = 36928 - 11753 pi
P1 = 30784 - 9798 pi
P0 = 6912 - 2200 pi
Q1 = 11743 - 7475 pi/2
Q0 = P0
with a |rel. error| < 2.5*10^-7 for n>=0.
Error profile:
n rel. error n rel. error
----------------------------------------
0 0 12 -2.323*10^-7
1 0 13 -2.390*10^-7
2 0 14 -2.431*10^-7
3 0 15 -2.453*10^-7
4 0 16 -2.459*10^-7
5 -3.706*10^-8 17 -2.454*10^-7
6 -8.367*10^-8 18 -2.440*10^-7
7 -1.263*10^-7 19 -2.420*10^-7
8 -1.611*10^-7 20 -2.394*10^-7
9 -1.879*10^-7 30 -2.053*10^-7
10 -2.078*10^-7 40 -1.740*10^-7
11 -2.222*10^-7 50 -1.496*10^-7
Best regards,
Knud Thomsen
David W. Cantrell
> An interesting type of approximation to the central binomial
> coefficient is of the form:
>
> C(2n, n) ~= 4^n / sqrt( Rm(n) )
>
> Rm being a rational function of max. degree m+1 (m>0):
>
> Rm(n) = (pi n^(m+1) + sum(i=0,m) Pi n^i) / (n^m + sum(i=0,m-1) Qi n^i)
>
> and where the 2m+1 coefficients are defined by simply requiring exact
> results for 2m>=n>=0; note that C(0,0)=1 implies that Q0=P0.
Hello, Knud!
Yes, your form of approximation is nice.
FWIW, here are simple upper and lower bounds for C(2n, n).
Upper bound: 4^n / sqrt(pi(n + 1/4)) (Ub)
Lower bound: Ub * (1 - 1/(8(n + 1/4))^2) (Lb)
Your approximations are precise for small n, while the relative errors of
my bounds at n = 0 are roughly 13% and -15%, resp. But for large n, those
bounds make reasonably good approximations. For example, at n = 50, their
relative errors are about 6*10^-6 and -4*10^-10, resp.
Best regards,
David W. Cantrell
sa...@kt-algorithms.com
>
> - Show quoted text -
Thanks, David!
Best regards,
Knud
Rob Johnson
David W. Cantrell <DWCan...@sigmaxi.net> wrote:
>"sa...@kt-algorithms.com" <sa...@kt-algorithms.com> wrote:
>> An interesting type of approximation to the central binomial
>> coefficient is of the form:
>>
>> C(2n, n) ~= 4^n / sqrt( Rm(n) )
>>
>> Rm being a rational function of max. degree m+1 (m>0):
>>
>> Rm(n) = (pi n^(m+1) + sum(i=0,m) Pi n^i) / (n^m + sum(i=0,m-1) Qi n^i)
>>
>> and where the 2m+1 coefficients are defined by simply requiring exact
>> results for 2m>=n>=0; note that C(0,0)=1 implies that Q0=P0.
>
>Hello, Knud!
>
>Yes, your form of approximation is nice.
>
>FWIW, here are simple upper and lower bounds for C(2n, n).
>
>Upper bound: 4^n / sqrt(pi(n + 1/4)) (Ub)
>
>Lower bound: Ub * (1 - 1/(8(n + 1/4))^2) (Lb)
>
>Your approximations are precise for small n, while the relative errors of
>my bounds at n = 0 are roughly 13% and -15%, resp. But for large n, those
>bounds make reasonably good approximations. For example, at n = 50, their
>relative errors are about 6*10^-6 and -4*10^-10, resp.
Using Stirling's assymptotic series, we get that the central binomial
coefficient is assymptotically
4^n 1 1 5 21
---------- ( 1 - --- + ------- + -------- - --------- - ... )
sqrt(pi n) 8 n 128 n^2 1024 n^3 32768 n^4
which, using the first 3 terms, gives
n C(2n,n) approximation
- ------- -------------
1 2 1.99229446690301
2 6 5.99660115228404
3 20 19.9965102093602
4 70 69.9947702088935
5 252 251.990291239197
Multiply by sqrt(1 + 1/(4n)) / sqrt(1 + 1/(4n)) to get
4^n 1 1 3
--------------- ( 1 - ------ + ------- - -------- - ... )
sqrt(pi(n+1/4)) 64 n^2 128 n^3 8192 n^4
Substituting m = n+1/4, we get
4^m 1 21
----------- ( 1 - ------ + -------- - ... )
sqrt(2pi m) 64 m^2 8192 m^4
Using one and two terms in the series, we get your approximations.
When n = 0, the third term throws things awry as is often the case
with assymptotic expansions.
The interesting part is that out to the 1/m^50 term, the series is
even. This would indicate that C(2m-1/2,m-1/4) 4^{-m} sqrt(m) is
even. I have not had a chance to look into this yet.
Rob Johnson <r...@trash.whim.org>
take out the trash before replying
to view any ASCII art, display article in a monospaced font
Rob Johnson
Rob Johnson <r...@trash.whim.org> wrote:
>assymptotic
Make that asymptotic, etc.
Robert Israel
That can't be literally true. For example, C(2m-1/2,m-1/4) 4^(-m) sqrt(m)
has poles at m = 1/4 - k/2 for positive integers k.
--
Robert Israel isr...@math.MyUniversitysInitials.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada
Robert Israel
Let Q = C(2m-1/2,m-1/4) 4^(-m) sqrt(m)
ln(Q) = ln(Gamma(2m+1/2)) - 2 ln(Gamma(m+3/4)) - 2 m ln(2) + ln(m)/2
(d/dm) ln(Q) = 2 Psi(2m+1/2) - 2 Psi(m+3/4) - 2 ln(2) + 1/(2m)
= Psi(m+1/4) - Psi(m+3/4) + 1/(2m)
Now it looks to me like Psi(m+t) - Psi(m+1-t) has only odd powers of m in its
asymptotic series. Indeed
Psi(m+t) - Psi(m+1-t)
= 2 sum_{j=0}^infty Psi(2j+1, m+1/2)/(2j+1)! (t-1/2)^(2j+1)
where Psi(k,x) is the k'th derivative of Psi(x).
Now asymptotically
Psi(m) = ln(m) - 1/(2m) + (terms in even powers of m)
from the Euler-Maclaurin formula and the fact that bernoulli(k) = 0
when k > 1 is odd. Using the identity
Psi(m+1/2) = 2 Psi(2 m) - Psi(m) - 2 ln(2)
the terms in 1/m cancel, so
Psi(m+1/2) = ln(m) + (terms in even powers of m).
Taking derivatives, we find that Psi(k,m+1/2) has only odd powers of m
when k is an odd integer and only even powers of m when k is an even
integer. Up to some questions of interchanging asymptotics and sums,
this completes the proof.