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 
 A: 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*}
A: 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})$.
A: 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}
$$
