(a) Let $C_n$ denote the number of ways of writing a valid list of open and closed parentheses of length $2n$ (valid means that at any point along the list, the number of open parentheses must be greater than or equal the number of closed parentheses). In the case of $n = 3$, there are 5 valid configurations:
((())), (())(), ()()(), (()()), ()(())
With $C_0 = 1$, provide a combinatorial proof that
$C_{n+1} = C_0C_n + C_1C_{n-1} + …. + C_kC_{n-k} + …C_nC_0$
(b) Show that $C_n$ also determines the number of paths in the plane from $(0, 0)$ to $(n, n) \in \mathbb{N} \times \mathbb{N}$, that always stay above the main diagonal $(y = x)$ if each step in the path is of the form $(1, 0)$, or $(0, 1)$ (i.e., unit distance due east or due north).
I can't seem to figure out this problem.
Hint. For a valid bracket word of length $2n+2$, the first symbol must be a left bracket. This will at some stage be matched by a right bracket. So the word looks like $$(\cdots)\cdots$$ where each $\cdots$ is a valid bracket word. These two words between them contain $2n$ symbols. See if you can finish the argument from here.