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 

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*}
