Lesson 3

Theorem. For Catalan numbers, the following formula holds: \[C(n)=\frac{1}{n+1}\cdot \binom{2n}{n}\ .\]

From the bounds on binomial coefficients, the asymptotic behavior of Catalan numbers is: \[C(n) = \Theta\left( \frac{4^n}{n^{3/2}}\right) \ .\]

Several dozen proofs of the formula are known. We will consider three of them below.