# Proof of recursive formula for Catalan numbers, and their interpretation as the number of paths

If $C_n$ is the $n$th Catalan number, then show that they satisfy the following recurrence:

$$C_0 = 1,\quad C_{n+1} = C_0C_n + C_1C_{n−1}+ \cdots + C_kC_{n−k} + \cdots + C_nC_0\text{ ?}$$

I tried using a bijective proof with $n+1$ appearing in the denominator of the formula $C_n$.

Also, I need to show that $C_n$ determines the number of paths in the plane from $(0, 0)$ to $(n, n) \in\mathbb N\times\mathbb N$, that don’t cross the main diagonal ($y = x$) if each step in the path is of the form $(1, 0)$, or $(0, 1)$.

Any suggestions would help!

Edit: $C_n$ denotes the valid list of open and closed parentheses of length $2n$ (valid meaning the number of open parentheses is greater than or equal to closed parentheses)

• I reformatted the post. See math notation guide. – user147263 Sep 6 '14 at 22:45
• What definition are you using for the Catalan numbers? – Thomas Andrews Sep 6 '14 at 22:47

By tilting things $45^{\circ}$, consider paths from $0$ to $2n$ of slope $+1$ and $-1$ and length $\sqrt 2$ to define $C_n$. Take any path of length $n+1$ (so $n+1$ ups and $n+1$ downs), and consider the first time it touches the line $x=y$. It is a number $2(k+1)$ with $0\leqslant k\leqslant n$. We can split the path into the part where it first touches the $x$-axis, which is a Catalan path of length $k+1$. But since this is the first time it touches the $x$-axis, we can look at the line $y=1$, i.e. one step above, and still get a bona-fide Catalan path, of length $k$. The remainder is a Catalan path of length $n+1-(k+1)=n-k$. This gives a bijection between glued up Catalan paths of length $k$ and ${n-k}$ and the Catalan paths of length $n+1$ that first touch the $x$-axis at place $k+1$. Doing this for each $k$ gives the result, i.e. that $$C_{n+1}=\sum_{k=0}^n C_kC_{n-k}$$
In the definition of the valid list of opening and closing parentheses (vlp for short), it does not suffice to require that the number of opening parentheses equals the number of closing parentheses. In addition one has to require that in each left prefix (i. e. sublist) the number of opening parentheses is no less than the number of closing ones. Then, the bijection with paths above main diagonal is clear: start reading the list and make move $(1,0)$ when encountering an opening parenthesis and move $(0,1)$ when encountering a closing parenthesis.
For a vlp $l$ of any length, denote by $(l)$ the list obtained by enclosing $l$ into a new pair of parentheses. Moreover, if $l$ is of positive length (i. e. nonempty), denote by $\operatorname{Left}l$ and $\operatorname{Right}l$ two lists obtained as follows: since $l$ is nonempty, it begins with an opening parenthesis. Find a closing parenthesis that matches it. This gives you a nonempty sublist $l'$. Then let $\operatorname{Left}l$ be the list obtained by removing outer pair of parentheses from $l'$, and let $\operatorname{Right}l$ be the list obtained by removing $l'$ from $l$. Assigning to $l$ the pair $\left\langle\operatorname{Left}l,\operatorname{Right}l\right\rangle$ gives the desired bijection. The inverse bijection is clear - to a pair $\left\langle l_1,l_2\right\rangle$ of vlp's it assigns the concatenation of $(l_1)$ with $l_2$. Clearly each nonempty vlp is of this form for unique $l_1$ and $l_2$ (given by $\operatorname{Left}l$ and $\operatorname{Right}l$ respectively).