Catalan numbers derivation (quadratic part)

116 Views Asked by At

When deriving the Catalan numbers using generating functions, eventually you reach the step:

$C(x) = 1 + xC(x)^2$

which means

$xC(x)^2 - C(x) + 1 = 0$

Which, through the quadratic formula, means

$C(x) = \frac{1 \pm \sqrt{1 - 4x}}{2x}$

But most derivations go forward with the assumption that the $\pm$ is actually a $-$ instead of a $+$. There should be two solutions but they move forward as if there is only one.

What is wrong with going forward with $+$?

1

There are 1 best solutions below

0
On BEST ANSWER

This happens because if : $$C(x)=\frac{1+\sqrt{1-4x}}{2x}$$ then letting $x \to 0^{+}$ all the terms in the powers series (except $C_0$ ) vanish so :

$$C_0 =\lim_{x \to 0^{+}} C(x)=\lim_{x \to 0^{+}} \frac{1+\sqrt{1-4x}}{2x}=\infty$$

But $C_0=1$ so this is a contradiction .

But if we try with the other then , using l'Hospital's :

$$\lim_{x \to 0^{+}} \frac{1-\sqrt{1-4x}}{2x}=\lim_{x \to 0^{+}}\frac{-\frac{1}{2} \cdot (-4)}{2\sqrt{1-4x}}=1 $$ and this agrees with $C_0=1$ .