# Section8.3Solving Equations

If $C(t)$ denotes the generating series for the Catalan numbers, then

$C(t) = 1+tC(t)^2.$
From this it follows that
$C(t) = \frac{1}{2t}(1-\sqrt{(1-4t)}).$
We can implement this as follows:

The first coefficients are what we expect:

If

$\Phi(u) := 1+tu^2$
then our equation for $C(x)$ about may be written as
$C(t) = \Phi(C(t));$
hence $C(t)$ is defined as a fixed point of a map on $\rats[[t]]$. We can solve this directly. Recursively define a sequence of series $C_i(t)$ by $C_0(t)=1$ and $C_{n+1}(t) =\Phi(C_n(t))$. We then find that
\begin{align*} C_1(t) &= 1 + t\\ C_2(t) &= 1 + t + 2t^2 + t^3\\ C_3(t) &= 1 + t + 2t^{2} + 5t^{3} + 6t^{4} + 6t^{5} + 4t^{6} + t^{7}. \end{align*}
and we see that the coefficients of $C_n(t)$ are accurate up to (and including) degree $n$. (At least for $n\le3$, but it's easy to verify this holds for larger values of $n$.) One problem here is that if we continue in this vein, our expression for $C_k(t)$ will have $2^k$ terms, of which only the first $k+1$ are sure to be accurate. The following code avoids this extra work.

As an exercise, verify that if the first $k+1$ coefficients of $C_k(t)$ are correct, then the first $k+2$ coefficients of $C_{k+1}(t)$ are correct.