<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] 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*}
</s>