Calculating Catalan numbers using Chebyshev's inequality

Question

By using Chebyshev's inequality $P(|X - E[X]| \geq \varepsilon) \leq \operatorname{Var}(X)/ \varepsilon^2$ I want to calculate the following estimation for the Catalan numbers $C_n = \frac{1}{n+1} \binom{2n}{n}$ :

$$C_n \geq \frac{4^{n-1}}{(n+1)(\sqrt{n} + \frac{1}{2})} \forall n \in \mathbb N.$$

Hint is to use a random variable $X$ which is binomial distributed, in a way that there's $\frac{1}{2}$ on the right side of Chebyshev's inequality for $\varepsilon = \sqrt{n}$, and that $\binom{2n}{n}$ is the largest binomial coefficient among $\binom{2n}{k}, k \in \{0, \ldots, 2n \}$. I got that for $X \sim \mathrm{Bin}(2n,\frac{1}{2})$. Can anybody show me how to move on?

Answer 1

Based on Chebyshev, you should have:

$$ P(|X - n| \ge \sqrt{n}) \le \frac12 $$

Taking the complement of the above event:

$$ 1 - P(n - \sqrt{n} < X < n +\sqrt{n}) \le \frac 12 $$ $$ \frac12 \le P(n - \sqrt{n} < X < n + \sqrt{n}) $$

Rewrite the above probability in terms of a binomial sum, and bind it from above using that $\binom{2n}{n}$ is the largest contributor of the sum. Multiply both sides by $1/(n+1)$, rearrange and do some easy algebra to get the claimed inequality.