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)
Best Answer
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}$$