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?


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.

  • $\begingroup$ I have problems to bind it the sum from above, can you show me how to do this a bit more detailed? $\endgroup$ – xxx Nov 23 '14 at 13:35
  • $\begingroup$ @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. $\endgroup$ – George V. Williams Nov 23 '14 at 22:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.