# Finding generating function of binary tree using quadratic formula?

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

• Solve for $y$ in $y=1+xy^2$ and then try to compute taylor expansion of a square root you will get. – Phicar Oct 19 '16 at 17:17
• I can get the two formulas by solving for y, but I'm still not sure where to go from there – PCR Oct 19 '16 at 17:56
• Use differentiation, you should look a little bit about Taylor expansion. – Phicar Oct 19 '16 at 18:34

## 1 Answer

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.