Since $D(x)=xC(x)=(1-\sqrt{1-4x})/2$,
$$
\frac1{1-D(x)-D(tx)}
=\frac2{\sqrt{1-4x}+\sqrt{1-4tx}}.
$$
Rationalizing and using the Catalan generating function gives
$$
\frac2{\sqrt{1-4x}+\sqrt{1-4tx}}
=\sum_{n\geq0}C_nx^n(1+t+\cdots+t^n).
$$
Thus the coefficient of every $t^k$, $0\leq k\leq n$, is $C_n$. The number of bridges with exactly $2k$ negative steps is consequently independent of $k$.


Solution

Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 145 / 3 / d / Solution

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2026/iii/paper-145/3/d/solution