algorithm - 反证中心二项式系数的渐近下界

Question

我最近正在学习二项式系数，并且想知道如何反驳 2nCn(或中心二项式系数)的下限不是 4^n；换句话说:

可以轻松构建一些极其慷慨的界限，例如:

我试图通过反证法来证明，所以假设:

显然，c₁ 不可能存在，因为当 n 接近无穷大时 1/(2n + 1) 接近 0。还可以看出 c₂ 必须驻留在 (0, 1] 中。而且...我被困住了。直观上，很明显 c₂ 不能存在。

我知道有人提出了类似的问题here ，但并没有提供真正的证据。我还知道，当 n 接近无穷大时，您可以证明 2nCn/4ⁿ 的极限接近 0，但我想知道是否还有另一种方法可以做到这一点 - 特别是通过证明 c< sub>2 不能存在。

Answer 1

对于所有 n，常数 c₂ 的上限必须为

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),

因此它不可能是正数。