# Calculating Catalan numbers using Chebyshev's inequality

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?

$$P(|X - n| \ge \sqrt{n}) \le \frac12$$
$$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.
• @xxx: you should get something like $\sum_k \binom{2n}{k}$ from $n-\sqrt{n}$ to $n+\sqrt{n}$, once you factor out a constant term of $1/4^n$. This sum is less than $\sum_k \binom{2n}{n}$ since that is the largest term in the sum. Then its just a sum of a constant term, which you can treat as usual. If you still need elaboration, tell me and I'll write up the full solution. – George V. Williams Nov 23 '14 at 22:06