I know that the generating function for the Catalan numbers sequence$$1 + 2x + 5x^2 + 14x^3 + ....$$ is $$C(x) = \frac{1 \pm \sqrt{1-4x}}{2x}$$

But I want to know why do choose $$C(x) = \frac{1 - \sqrt{1-4x}}{2x}$$

over the plus $$C(x) = \frac{1 + \sqrt{1-4x}}{2x}$$

Is there a simple explanation for that ?


We know from the series expansion that $C(0)=1$, so

$$1=C(0)=\lim_{x\to 0}\frac{1\pm\sqrt{1-4x}}{2x}\;.$$

If we choose the plus sign, the limit clearly doesn’t exist, since the numerator approaches $2$ while the denominator approaches $0$. Thus, we take the minus sign, so that the limit is a $\frac00$ indeterminate form, and verify that it actually is $1$.


The equation leading to this expression of the Catalan generating function is the following :

$$XZ^2-Z+1=0 $$

Where we need to solve this in $\mathbb{C}[[X]]$, the unkown being $Z$.

When we solve it using discriminant (the usual method for equations of degree 2), one must not forget that we de not solve it in $\mathbb{C}[[X]]$ but in $Frac(\mathbb{C}[[X]])=\mathbb{C}((X))$ the field of Laurent series.

As a reminder :

$$\text{ elements of }\mathbb{C}[[X]]\text{ are called formal power series or generating functions and a typical element is } \sum_{n\geq 0} a_nX^n $$

$$\text{ elements of }\mathbb{C}((X))\text{ are called Laurent series and a typical element is } \sum_{n\geq N} a_nX^n $$

Where $N\in\mathbb{Z}$. In other words when you have your two solutions of your equation you get :

$$Z_{\pm}(X)=\frac{1\pm \sqrt{1-4X}}{2X} $$

Now by a straightforward analysis we know that :

$$Z_-(X)\notin \mathbb{C}[[X]]\text{ and } Z_+(X)\in \mathbb{C}[[X]]$$

Since the Catalan generating function has been shown to be a solution of this equation and that it is a generating function by definition, it follows that it cannot but be $Z_+$ which is the only generating function among the solution of the equation.


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.