# Showing Directly that Dyck Paths Satisfy the Catalan Recurrence

How would one show, without appealing to a bijection with a well known problem, that Dyck Paths satisfy the Catalan recurrence?

• Isn't this the Segner recurrence for Catalan numbers? Dec 6 '20 at 17:13

There are at least two different definitions of Dyck path; I prefer to think of them as mountain ranges, i.e., paths from $\langle 0,0\rangle$ to $\langle 2n,0\rangle$, using steps $\langle 1,1\rangle$ and $\langle 1,-1\rangle$, that do not drop below the $x$-axis. If you think of them as lattice paths from $\langle 0,0\rangle$ to $\langle n,n\rangle$ that do not rise above the diagonal line $y=x$, it’s not hard to make the conversion: your step to the right is my up-step, your step up is my down-step, and the diagonal line corresponds to my $x$-axis.
Let $P$ be a Dyck path of length $2(n+1)$, and let $\langle 2k,0\rangle$ be the first point to the right of $\langle 0,0\rangle$ at which $P$ hits the $x$-axis. The part of $P$ from $\langle 0,0\rangle$ to $\langle 2k,0\rangle$ is a Dyck path of length $2(k-1)$ preceded by an up-step and followed by a down-step, and the part of $P$ from $\langle 2k,0\rangle$ to $\langle 2(n+1),0\rangle$ is a Dyck path of length $2(n+1-k)$. There are $C_{k-1}$ Dyck paths of length $2(k-1)$, and there are $C_{n+1-k}$ Dyck paths of length $2(n+1-k)$. Finally, $k$ ranges from $1$ through $n+1$, so
$$C_{n+1}=\sum_{k=1}^{n+1}C_{k-1}C_{n+1-k}=\sum_{k=0}^nC_kC_{n-k}\;.$$
The Dyck language $$D$$ is given by the BNF description $$D = \epsilon \mid \mathtt( ~ D ~ \mathtt) ~ D \qquad\text{where \epsilon is the empty word}.$$ (the parentheses are literals, and the language consists of balanced strings of parentheses). Interpreting the opening and closing parentheses as up-steps respectively down-steps (both with a fixed sideways component), the total level along the path never drops below $$0$$, and is $$0$$ at the end of the path.
This grammar is non-ambiguous: every Dyck word matches it (recursively) in a unique manner. It follows that there is one Dyck word of length $$0$$, and that the number of Dyck words of length $$n+1$$ eqals the number of ordered pairs of Dyck words of combined length $$n$$. That is the Catalan recurrence.