Asymptotic approximation of Catalan Numbers

Question

The nth Catalan number is : $$C_n = \frac {1} {n+1} \times {2n \choose n}$$ The problem 12-4 of CLRS asks to find : $$C_n = \frac {4^n} { \sqrt {\pi} n^{3/2}} (1+ O(1/n)) $$ And Stirling's approximation is: $$n! = \sqrt {2 \pi n} {\left( \frac {n}{e} \right)}^{n} {\left( 1+ \Theta \left(\frac {1} {n}\right) \right)} $$ So, the nth catalan number becomes : $$C_n = \frac {2n!}{(n+1)(n!)^2} $$ That, after applying Stirling's approximation becomes: $$C_n = \left( \frac {1}{1+n} \right) \left( \frac {4^n}{\sqrt{\pi n}} \right) \frac {1}{\left( 1+\Theta \left(1/n\right) \right)}$$ And then, it becomes hopeless. The Asymptotic bound comes in the denominator, not in the numerator.
What should be done now?

Any help appreciated.
Moon

Answer 1

Use the binomial approximation for $(1+y)^k$:

$$ (1+y)^k=1+ky+\Theta(y^2) $$ as $y \to 0$.

In your case, you can take $k=-1$ to show that any function which is $\frac{1}{1+\Theta(1/n)}$ is also $1+\Theta(\frac{1}{n})$.

Answer 2

In this answer, it is shown that $$ \frac{4^n}{\sqrt{\pi(n+\frac13)}}\le\binom{2n}{n}\le\frac{4^n}{\sqrt{\pi(n+\frac14)}}\tag{1} $$ Using the fact that as $n\to\infty$, $$ \begin{align} (n+a)^b &=n^b\left(1+\frac an\right)^b\\ &=n^b\left(1+O\left(\frac1n\right)\right)\tag{2} \end{align} $$ we get $$ \binom{2n}{n}=\frac{4^n}{\sqrt{\pi n}}\left(1+O\left(\frac1n\right)\right)\tag{3} $$ Furthermore $$ \frac1{n+1}=\frac1n\left(1+O\left(\frac1n\right)\right)\tag{4} $$ Therefore, $$ \frac1{n+1}\binom{2n}{n}=\frac{4^n}{\sqrt{\pi}n^{3/2}}\left(1+O\left(\frac1n\right)\right)\tag{5} $$

Answer 3

We can use Stirling's approximation formula \begin{align*} n!=\sqrt{2\pi n}\left(\frac{n}{e}\right)^n\left(1+O\left(\frac{1}{n}\right)\right) \end{align*} to prove:

The following is valid

\begin{align*} C_n=\frac{1}{n+1}\binom{2n}{n}= \frac {4^n} { \sqrt {\pi} n^{3/2}} (1+ O(1/n)) \tag{1} \end{align*}

We obtain using (1) \begin{align*} \frac{1}{n+1}\binom{2n}{n}&=\frac{1}{n+1}\cdot\frac{(2n)!}{n!n!}\\ &=\frac{1}{n+1}\cdot\sqrt{4\pi n}\left(\frac{2n}{e}\right)^{2n}\left(1+O\left(\frac{1}{n}\right)\right)\\ &\qquad \cdot \left(\frac{1}{\sqrt {2 \pi n} {\left( \frac {n}{e} \right)}^{n} {\left( 1+ O \left(\frac {1} {n}\right) \right)}}\right)^2\\ \\ &=\frac{1}{n+1}\cdot\frac{4^n}{\sqrt{\pi n}}\cdot \frac{\left(1+O\left(\frac{1}{n}\right)\right)}{\left(1+O\left(\frac{1}{n}\right)\right)\left(1+O\left(\frac{1}{n}\right)\right)}\tag{2}\\ &=\frac{1}{n\left(1+O\left(\frac{1}{n}\right)\right)}\cdot\frac{4^n}{\sqrt{\pi n}} \left(1+O\left(\frac{1}{n}\right)\right)^3\tag{3}\\ &=\frac{1}{n}\cdot\frac{4^n}{\sqrt{\pi n}} \left(1+O\left(\frac{1}{n}\right)\right)^4\\ &=\frac{4^n}{\sqrt{\pi}n^{3/2}} \left(1+O\left(\frac{1}{n}\right)\right)\tag{4}\\ \end{align*} and the claim follows.

Comment:

• In (2) we do some cancellation

• In (3) we use the geometric series expansion \begin{align*} \frac{1}{1+O\left(\frac{1}{n}\right)}=1+O\left(\frac{1}{n}\right) \end{align*}

• In (4) we use \begin{align*} \left(1+O\left(\frac{1}{n}\right)\right)\left(1+O\left(\frac{1}{n}\right)\right)=1+O\left(\frac{1}{n}\right) \end{align*}