\( \newcommand\al{\alpha} \newcommand\be{\beta} \newcommand\de{\delta} \newcommand\De{\Delta} \newcommand\eps{\epsilon} \newcommand\ga{\gamma} \newcommand\Ga{\Gamma} \newcommand\ka{\kappa} \newcommand\la{\lambda} \newcommand\La{\Lambda} \newcommand\om{\omega} \newcommand\Om{\Omega} \newcommand\sg{\sigma} \newcommand\Sg{\Sigma} \renewcommand\th{\theta} %--- Latex uses \th for a Norse character \newcommand\Th{\Theta} \newcommand\vphi{\varphi} % % some calligraphy % \newcommand\cA{{\mathcal A}} \newcommand\cB{{\mathcal B}} \newcommand\cC{{\mathcal C}} \newcommand\cD{{\mathcal D}} \newcommand\cE{{\mathcal E}} \newcommand\cF{{\mathcal F}} \newcommand\cG{{\mathcal G}} \newcommand\cH{{\mathcal H}} \newcommand\cI{{\mathcal I}} \newcommand\cJ{{\mathcal J}} \newcommand\cK{{\mathcal K}} \newcommand\cL{{\mathcal L}} \newcommand\cM{{\mathcal M}} \newcommand\cN{{\mathcal N}} \newcommand\cO{{\mathcal O}} \newcommand\cP{{\mathcal P}} \newcommand\cQ{{\mathcal Q}} \newcommand\cR{{\mathcal R}} \newcommand\cS{{\mathcal S}} \newcommand\cT{{\mathcal T}} \newcommand\cU{{\mathcal U}} \newcommand\cV{{\mathcal V}} % % fields and rings (and a semigroup) % \newcommand\cx{{\mathbb C}}% complexes \newcommand\fld{{\mathbb F}} \newcommand\flde{{\mathbb E}} \newcommand\ints{{\mathbb Z}} \newcommand\nn{{\mathbb N}}%non-negative integers \newcommand\re{{\mathbb R}}%reals \newcommand\rats{{\mathbb Q}} % % the really useful stuff % \newcommand\comp[1]{{\mkern2mu\overline{\mkern-2mu#1}}} \newcommand\diff{\mathbin{\mkern-1.5mu\setminus\mkern-1.5mu}}% for \setminus \newcommand\res{\mathbin{\mkern-2.0mu\restriction\mkern-2.0mu}} \newcommand\sbs{\subseteq} \newcommand\sps{\supseteq} \newcommand\seq[3]{#1_{#2},\ldots,#1_{#3}} \DeclareMathOperator{\supp}{supp} \DeclareMathOperator{\im}{im} \DeclareMathOperator{\row}{row} \newcommand\pmat[1]{\begin{pmatrix} #1 \end{pmatrix}} \newcommand\cprod{\mathbin{\square}} \newcommand\gbin[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}} % % matrix theory % \newcommand\ip[2]{\langle#1,#2\rangle} \newcommand\one{{\bf1}} \DeclareMathOperator{\rk}{rk} \DeclareMathOperator{\tr}{tr} \DeclareMathOperator{\col}{col} \newcommand\mat[3]{\mathrm{Mat}_{#1\times #2}(#3)} \newcommand\sm[3]{\sum_{#1=#2}^{#3}} % % some group theory % \newcommand\aut[1]{{\rm Aut}(#1)} \newcommand\fx[1]{{\rm fix}(#1)}% ch2 \newcommand\grp[1]{\langle #1\rangle} \newcommand\nrml{\vartriangleleft} \newcommand\nrmleq{\trianglelefteq} \DeclareMathOperator{\Sym}{Sym} \newcommand\sym[1]{\Sym(#1)} \DeclareMathOperator{\Alt}{Alt} \newcommand\alt[1]{\Alt(#1)} \)

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.