A set of approximations the central binomial coefficient - sci.math

Message from discussion A set of approximations the central binomial coefficient

Rob Johnson

View profile

More options Jul 8, 11:08 pm

Newsgroups: sci.math

From: r...@trash.whim.org (Rob Johnson)

Date: Tue, 08 Jul 2008 18:08:04 GMT

Local: Tues, Jul 8 2008 11:08 pm

Subject: Re: A set of approximations the central binomial coefficient

  Reply to author
  |
  Forward
  | Print
  | View thread
  | Show original
  | Report this message
  | Find messages by this author
  

In article <20080706103816.687...@newsreader.com>,
David W. Cantrell <DWCantr...@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

Reply to author Forward