Disproving asymptotic lower bound of central binomial coefficient

user_9441062 0
Viewed 247

I was recently learning about binomial coefficients and was wondering about how to disprove 2nCn (or the central binomial coefficient) not being lower-bounded by 4^n; in other words:

Some extremely generous bounds can be easily constructed, such as the following:

eqn1

I sought to prove by contradiction, so to assume:

eqn2

Clearly, c1 cannot exist, since 1/(2n + 1) approaches 0 as n approaches infinity. It can also be seen that c2 must reside in (0, 1]. And... I'm stuck. Intuitively, it seems rather obvious that c2 cannot exist.

I am aware a similar question has been asked here, but there wasn't really a proof provided. I'm also aware that you could prove the limit of 2nCn/4n approaches 0 as n approaches infinity, but I was wondering if there was another way to do so - particularly, by proving that c2 cannot exist.

binomial-coefficients big-o complexity-theory algorithm
1 Answers

For all n, the constant c2 would have to be upper bounded by

2n choose n       (2n)!
----------- = -------------
    4^n       2^n n! 2^n n!

                  (2n)!
            = -------------
              (2n)!! (2n)!!

              (2n-1)!!
            = --------
               (2n)!!

                 n    (2i-1)
            = product ------
                i=1     2i

                 n
            = product (1 - 1/(2i))
                i=1

                 n
            ≤ product exp(-1/(2i))    [since 1 + x ≤ exp(x)]
                i=1

                   n
            = exp(sum -1/(2i))
                  i=1

            ≤ exp(-ln(n+1)/2)    [since sum ≤ integral of increasing fn]

            = 1/√(n+1),

hence it cannot be positive.

user_21446690
Related