> [!NOTE] > The [[Ordinary Generating Function|ordinary generating function]] of the [[Catalan Numbers|Catalan numbers]] is given by $f(x)=\sum_{n \geq 0} C_{n} x^n = \frac{1-\sqrt{ 1- 4x }}{2x}.$ ###### Proof: By definition, the Catalan numbers satisfy $C_{n}=\sum_{i=0}^{n-1}C_{i}C_{n-i}$ Applying the definition of Cauchy product yields $\begin{align} f(x)^2 &= \left( \sum_{n \geq 0} C_{n}x^n \right) \left( \sum_{n \geq 0} C_{n}x^n \right) \\ &= \sum_{n \geq 0}\left( \sum_{i=0}^{n} C_{i}C_{n-i} \right)x^n \\ &= \sum_{n \geq 0 } (C_{n+1}) x^n = \frac{1}{x}\sum_{n \geq 0} C_{n+1}x^{n+1} \\ &= \frac{1}{x} (f(x) -1). \end{align}$So by the quadratic formula, $f(x)= (1 \pm \sqrt{ 1-4x })/2x$. Now $\lim_{ x \to 0 } (1 + \sqrt{ 1-4x })/2x = \infty$ however, applying L'hopital's rule, $\lim_{ x \to 0 } (1 - \sqrt{ 1-4x })/2x = 0$ so we choose the minus sign.