Solve

\[ \begin{aligned} T_N &= \sum_{1 \le k < N} T_k T_{N-1-k} + \delta_{N0} \\ T(z) \equiv \sum_{N \ge 0} T_N z_N &= \sum_{N \ge 0} \sum_{1 \le k < N} T_k T_{N-1-k}\, z^N + 1 & \text{multiply by }z^N \text{ and sum over all }N \\ &= 1 + \sum_{k \ge 0} \sum_{N > k} T_k T_{N-1-k}\, z^N & \text{switch summation order} \\ &= 1 + \sum_{k \ge 0} \sum_{N \ge 0} T_k T_{N}\, z^{N+k+1} & \text{change }N \text{ to } N+k+1 \\ &= 1 + z\big(\sum_{k \ge 0} T_k z^k\big) \big(\sum_{N \ge 0} T_{N} z^N\big) & \text{distribute} \\ T(z) &= 1 + z T(z)^2 \\ T(z)^2 - \frac{T(z)}{z} &= -\frac{1}{z} \\ \big(T(z) - \frac{1}{2z}\big)^2 &= -\frac{1}{z} + \frac{1}{4z^2} = \frac{1-4z}{4z^2} \\ T(z) - \frac{1}{2z} &= \frac{\pm \sqrt{1-4z}}{2z} \\ \therefore zT(z) &= \frac{1}{2} ( 1 \pm \sqrt{1-4z}) \\ &= \frac{1}{2} ( 1 \pm (1-4z)^{1/2}) \\ &= \frac{1}{2} \big( 1 \pm \sum_{N \ge 0} {\frac{1}{2} \choose N} (-4z)^N \big) & \text{binomial theorem} \\ &= \frac{1}{2} \big( 1 \pm (1 + \sum_{N \ge 1} {\frac{1}{2} \choose N} (-4z)^N ) \big) \\ zT(z) &= -\frac{1}{2} \sum_{N \ge 1} {\frac{1}{2} \choose N} (-4z)^N & \text{pick the minus sign} \\ T(z) &= -\frac{1}{2} \sum_{N \ge 1} {\frac{1}{2} \choose N} (-4)^N z^{N-1} \\ &= -\frac{1}{2} \sum_{N \ge 0} {\frac{1}{2} \choose N+1} (-4)^{N+1} z^{N} & \text{re-index} \\ [z^N]T(z) \equiv T_N &= -\frac{1}{2} {\frac{1}{2} \choose N+1} (-4)^{N+1} \\ T_N &= -\frac{1}{2} \frac{\frac{1}{2} (\frac{1}{2}-1) (\frac{1}{2}-2) \cdots (\frac{1}{2}-N)}{(N+1)!} (-4)^{N+1} &\text{expand via definition} \\ &= -\frac{1}{2} \frac{\frac{1}{2} (\frac{1}{2}-1) (\frac{1}{2}-2) \cdots (\frac{1}{2}-N)}{(N+1)!} (-2)^{N+1} 2^{N+1} \\ &= \frac{(-\frac{1}{2}) (\frac{1}{2}-1) (\frac{1}{2}-2) \cdots (\frac{1}{2}-N)}{(N+1)!} (-2)^{N+1} 2^N \\ &= \frac{1 \cdot 3 \cdot 5 \cdots (2N-1)}{(N+1)!} 2^N &\text{distribute } (-2)^{N+1} \text{ among factors} \\ &= \frac{1 \cdot 3 \cdot 5 \cdots (2N-1)}{(N+1)!} \cdot \frac{2 \cdot 4 \cdot 6 \cdots 2N}{1 \cdot 2 \cdot 3 \cdots N} &\text{expand out }2^N \\ &= \frac{1}{N+1}\cdot \frac{1 \cdot 3 \cdot 5 \cdots (2N-1)}{N!} \cdot \frac{2 \cdot 4 \cdot 6 \cdots 2N}{1 \cdot 2 \cdot 3 \cdots N} \\ &= \frac{1}{N+1}\cdot \frac{2N!}{N!\, N!} \\ T_N &= \frac{1}{N+1} {2N \choose N} & \text{the Catalan number}\\ \end{aligned} \]

\(\Box\)

Source: Analysis of Algorithm

# posted by rot13(Unafba Pune) @ 10:05 PM