## Solving 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:

Rt.<t> = QQ[[]]
Ct = (1/2)*(1-(1-4*t).sqrt()).shift(-1)


The first coefficients are what we expect:

Ct.O(9)

1 + t + 2*t^2 + 5*t^3 + 14*t^4 + 42*t^5 + 132*t^6 + 429*t^7 + 1430*t^8 + O(t^9)


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.

def iter( Fun, init, acc, n):
val = init
for i in [1..n]:
val = Fun( val).O(acc)
acc += 1


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.