Reasoning about the lower bound of ${{2n}\choose{n}}$

Question

A standard lower bound is ${{2n}\choose{n}} > \frac{4^n}{2n}$. For example, see this Wikipedia article.

It occurs to me that for higher $n$ using elementary arguments, this can be greatly improved.

By my calculations, for example, for $n \ge 94,070$:

$${{2n}\choose{n}} > \frac{4^n}{n^{11/20}}$$

Here's my reasoning:

• For $n = 94,070$

$\ln\left({{2n}\choose{n}}\right) > 130,402.4122$

$\ln\left(\frac{4^n}{n^{11/20}}\right) < 130,402.4121$

• Assume that that up to $n-1$, ${{2n-2}\choose {n-1}} > \frac{4^{n-1}}{(n-1)^{11/20}}$

• $(4n-2)^2 > 4^2(n^2-n) > (4n-4)^2$ $$(4n-2)^2\sqrt[9]{(4n-2)^2} > 4^2(n^2-n)\sqrt[9]{4^2(n-1)^2}$$ $$(4n-2)^{20} > 4^{20}(n^{9})(n-1)^{11}$$ $$(4n-2) > 4(n^{9/20})(n-1)^{11/20}$$ $$\frac{4n-2}{n(n-1)^{11/20}} > \frac{4}{n^{11/20}}$$

• ${{2n}\choose{n}} = \frac{(2n)(2n-1)}{n^2}{{2n-2}\choose{n-1}} = \frac{4n-2}{n}{{2n-2}\choose{n-1}}> \frac{(4n-2)(4^{n-1})}{(n)(n-1)^{11/20}} > \frac{4(4^{n-1})}{n^{11/20}}$

Am I wrong?

Answer 1

What you've done is basically correct. One small issue is that you wrote

Assume that that up to $n-1$, ${{2n-2}\choose {n-1}} > \frac{4^{n-1}}{(n-1)^{11/20}}$

However, this is not true in general as you've stated it, e.g., for $n = 3$, the LHS is 6 while the RHS is $10.9\ldots \;$. Note that all inductive proofs start with a base case, usually something small like $n = 0, 1, 2 \text{ or } 3$. In your case, the base value you're starting from is considerably larger, i.e., $94,070$. To make your statement correct, you should say something like "Assume for some $n - 1 \ge 94,070$ that ${{2n-2}\choose {n-1}} > \frac{4^{n-1}}{(n-1)^{11/20}}$". Since it's true for when $n - 1 = 94,070$, when you then show that it's also true for $n$, you've then completed the inductive procedure to show your inequality is true for all values $\ge 94,070$.

The next small issue is that in

$(4n-2)^2 > 4^2(n^2-n) > (4n-4)^2$

you don't need or use that $4^2(n^2-n) > (4n-4)^2$. For the multiplication you do to both sides of the first part of the inequality to hold only requires that what you're multiplying by, i.e., $\sqrt[9]{4^2(n-1)^2}$, is $\gt 0$, which is obviously true in this case.

Finally, here is what I believe is a somewhat simpler way to get from $(4n-2)^2 > 4^2(n^2-n)$ to your line of $(4n-2) > 4(n^{9/20})(n-1)^{11/20}$. This is by taking square roots of the first inequality to get

\begin{align} 4n - 2 &> 4n^{1/2}(n-1)^{1/2} \\ &= 4n^{9/20}n^{1/20}(n-1)^{11/20}(n-1)^{-1/20} \\ &= 4n^{9/20}(n-1)^{11/20}\left(\frac{n}{n-1}\right)^{1/20} \\ &> 4n^{9/20}(n-1)^{11/20} \end{align}