Formal power series and the quadratic formula I was recently reviewing a derivation of getting a formula for Catalan numbers in closed form. I understand the mechanics of the derivation, with the exception of one significant step:
If $f(x) = c_0 + c_1x +c_2x^2 + \cdots $ is the generating series for the Catalan numbers $c_n, n \geq 0$, then it satisfies the relation $xf(x)^2 - f(x) + 1 = 0$. But the next step of the proof is to solve for $f(x)$ by using the quadratic formula, which gives $f(x) = \frac{1 \pm \sqrt{1 - 4x}}{2x}$ (and then we take the 'minus' since the 'plus' doesn't work). My question is regarding the legality of applying the quadratic formula (qf) here. We initially learn the qf in elementary algebra, which is in the context of the $\textit{field}$ of real numbers. In particular, division and square roots are permitted. Here we are working with the $\textit{ring}$ of formal power series. Specifically, not all fps have multiplicative inverses, and indeed the fps $2x$ is not invertible. I see that the idea is that the numerator (after simplification) can be seen to have a factor of $x$, and so the idea is that we simply want to 'cancel' these two factors of $x$, but this strikes me as non-rigorous. I appreciate that we can prove we get the correct answer a posteriori (since it satisfies the recurrence relation that the Catalan numbers need to satisfy), but the actual method of finding the answer seems to be informal symbol manipulation based on our intuition of the qf in a field. So I suppose my specific question is:
Why are we allowed to divide by $x$ here when $x$ is not invertible in the ring of fps?
My guess is that it is allowed due to analytic convergence of the series on some positive radius of convergence, but I am really looking for some combinatorial/algebraic reasoning instead, which could potentially generalize to other situations. Does such reasoning exist?
If anyone could explain why performing the qf here is justifiable from a combinatorial/algebraic perspective, I would be very appreciative.
 A: $F=\Bbb{Q}((x))$ (the formal Laurent series $\sum_{n\ge -N} a_n x^n$ with rational coefficients) is a field so it works really the same way as over $\Bbb{R}$.
You need to check that the discriminant $1-4x$ of your quadratic polynomial $xT^2-T+1\in F[T]$ has a square root in $F$, which is $$a=\sum_{k\ge 0} {1/2\choose k} (-4x)^k\in F$$
Then $$xT^2-T+1= x(T-\frac{1+a}{2x})(T-\frac{1-a}{2x})\in F[T]$$ $f\in F$ is a root of $xT^2-T+1$ implies either that $f=\frac{1+a}{2x}$ or $f=\frac{1-a}{2x}$.
A: If $f$ has positive radius of convergence $R$, for any fixed $x\in(0,\,R)$ we know $f(x)$ is finite, and calculable by the method you've seen. (Note we no longer need to work in a ring of polynomials over a variable.) In particular, continuity at $x=0$ ensures $f(x)=\frac{1-\sqrt{1-4x}}{2x}$ for all such $x$.
So the hard question is how we know $R>0$; indeed, the convergence of $f$ for some $x$ of interest is necessary to prove $xf^2-f+1=0$. Alternatively, we can show $\frac{1-\sqrt{1-4x}}{2x}$ generates $\tfrac{1}{n+1}\binom{2n}{n}$ and this satisfies the initial conditions and recursion relation; the worst you can say about this reasoning is that it "got lucky".
