Chapter 8.4, Problem 43E

(Calculus required) Let $\left\{C_n\right\}$be the sequence of Catalan numbers, that is, the solution to the recurrence relation $C_n={\displaystyle {\sum }_{k-1}^{n-1}{C}_k{C}_{n-k-1}}$, With $C_0=C_1=1$ (see Example 5 in Section 8.1).

a) Show that if G(x) is the generating function for the sequence of Catalan numbers, then $xG{\left(x\right)}^2-G\left(x\right)+1=0$ . Conclude (using the initial conditions) that

$G\left(x\right)=\left(1-\sqrt{1-4x}\right)/\left(2x\right)$.

b) Use Exercise 42 to conclude that

$G\left(x\right)={\displaystyle \underset{n=1}{\overset{\infty }{\sum }}\frac{1}{n+1}\left(\begin{array}{c}2n\\ n\end{array}\right)x^n}$so that

$C_n=\frac{1}{n+1}\left(\begin{array}{c}2n\\ n\end{array}\right)$

c) Show that $C_0\ge 2^{n-1}$ for all positive integers n.