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.