I'm a bit stuck on this practice problem. Any help on how to solve it would be great. Thanks.
We will see that the generating function for ordered binary rooted trees is $T(x) = 1 + xT(x)^2$
i. Use the quadratic formula to find the two possible generating functions for
T(x).
ii. Use coefficient extraction to determine which generating function is correct
From your quadratic formula you can deduce $T(x) = \frac{1 \pm \sqrt{1 - 4 x}}{2x}$, solving (i). Which leaves the question, what sign to use (ii).
Luckily, we know the first terms of the genreating function $T(x)$: There is one tree without nodes and one tree with one node. This yields
$$T(x)= 1 + 1x + \ldots.$$
So the constant term should be $1$. But the constant term is $T(0)$. However, because of the fraction we cannot simply evaluate at $0$ but we may multiply the equation by the denominator. So we get
$$2x T(x) = 1 \pm \sqrt{1 - 4x} \; \Rightarrow \; 0 = 1 \pm \sqrt{1 - 0}.$$
Where the left equation is only true for $-$. Finally, we get
$$T(x) = \frac{1 - \sqrt{ 1 - 4x}}{2x}.$$
If you want to find the Taylor expansion of this expression, please refer to the first proof on the Wikipedia-Page of the Catalan numbers.