Lesson 1

Let \(\mathcal{S}(x)\) be the generating function of the Catalan number sequence \((1,1,2,5,14,42,\dotsc)\). The recurrence relation \[C(n)=\sum_{l+r=n-1}C(l)C(r)\] closely resembles a convolution. Indeed, \[\sum_{l+r=n-1}C(l)C(r)=[x^{n-1}](\mathcal{S}^{2}(x)) \ .\] Therefore, \[\mathcal{S}(x)=x\mathcal{S}^{2}(x)+1 \ ,\] which implies \[\mathcal{S}(x)=\frac{1 \pm \sqrt{1-4x}}{2x}\ .\] To determine which root to use, recall that \(\mathcal{S}(0)\) must equal one. Now, \(\frac{1 + \sqrt{1-4x}}{2x}\to \infty\) as \(x \to 0\), whereas \(\frac{1 - \sqrt{1-4x}}{2x}\to 1\) as \(x \to 0\) (for small \(x\), \(\sqrt{1-4x}\approx 1-2x\)).

from sympy import sqrt, limit
from sympy.abc import x

print(limit((1 + sqrt(1 - 4 * x)) / (2 * x), x, 0))
print(limit((1 - sqrt(1 - 4 * x)) / (2 * x), x, 0))

oo
1