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:

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.