<s>[INST] Asymptotic approximation of Catalan Numbers 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 
 [/INST] 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}
$$
</s>