6
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ $\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)$$ $\endgroup$ – robjohn Oct 26 '16 at 16:19
  • $\begingroup$ 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$. $\endgroup$ – Clement C. Oct 26 '16 at 16:22
  • $\begingroup$ @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. $\endgroup$ – Mooncrater Oct 27 '16 at 6:57
  • $\begingroup$ @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{.}$$ $\endgroup$ – robjohn Oct 27 '16 at 9:16
  • $\begingroup$ @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$.} $\endgroup$ – Mooncrater Oct 29 '16 at 2:26
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.