# 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

• $\frac1{1+O\left(\frac1n\right)}=1+O\!\left(\frac1n\right)$. For example, $$\frac1{1+\frac\alpha{n}}=1-\frac\alpha{n}+O\!\left(\frac1{n^2}\right)$$ – robjohn Oct 26 '16 at 16:19
• Just to elaborate: this is a special case of $(1+x)^\alpha = 1+\alpha x + O(x^2)$ for $x\to 0$, and any fixed $\alpha\in\mathbb{R}$. Here, take $x=1/n$ and $\alpha=-1$. – Clement C. Oct 26 '16 at 16:22
• @robjohn But, the definition of Big-O is: O(g(n)) = {f(n) : there exist positive constants c and n' such that 0<= f(n) <=c g(n) for all n>=n'.} .But we've a negative constant with the 1/n term. So, it can't engulf the O(1/n^2) term. – Mooncrater Oct 27 '16 at 6:57
• @Mooncrater: No. Straight from Wikipedia: One writes $$f(x)=O(g(x))\text{ as }x\to\infty$$ if and only if there is a positive constant $M$ such that for all sufficiently large values of $x$, the $\color{#C00000}{\text{absolute}}$ $\color{#C00000}{\text{value}}$ of $f(x)$ is at most $M$ multiplied by the absolute value of $g(x)$. That is, $f(x)=O(g(x))$ if and only if there exists a positive real number $M$ and a real number $x_0$ such that $$\left|f(x)\right|\le M\left|g(x)\right|\text{ for all }x\ge x_0\text{.}$$ – robjohn Oct 27 '16 at 9:16
• @robjohn But, that definition is from CLRS, and it clearly emphasizes on positive constants(3rd ed., page 47), it says:$O(g(n))$= {$f(n)$ : there exist positive constants $c$ and $n_0$ such that $0 \leq f(n) \leq cg(n)$ for all $n \geq n_0$.} – Mooncrater Oct 29 '16 at 2:26

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

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

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