Dyck Path

A path from to taking steps or
but never crossing strictly below the -axis

Theorem

There is Dyck Paths from to
where is the Catalan Number.

Proof

Suppose the path hits -axis for the first time at
where
Then we have a Dyck path
and one from .
Thus we find the recurrence

matching Catalan Numbers.