I was never really taught how to write a valid proof from some facts and a formula.
Could anyone help me out proving the following? $$ C_n = \begin{cases} 0, & n =0 \\ 1, & n = 1 \\\sum_{k=1}^{n-1} C_k \times C_{n-k}, & n\ge 2 \end{cases} $$
Using the fact that:
The number of triangulations of a convex polygon with $n+1$ vertices ($n\ge2$) is $C_n$
I thought about proving it by induction, as such I started showing that $C_2 = 1$ (and $C_3 = 2, C_4 =5$ to be sure).
I did that by:
Drawing the polygons and their triangulations
Calculating the value of each $C_n$ and showing that they were indeed equal!
Now, my problem is I don't know how to prove the inductive step.
Any help would be immensely appreciated!
Assume the formula is true up to some $n$. We want to show this formula holds for the case $n+1$.
$C_{n+1}$ is the number of triangulations of an $(n+2)$-gon. Fix an arbitrary edge $E$ of this $n+2$-gon and observe the following: For any triangulation, $E$ belongs to exactly one triangle, and there are $n$ possible such triangles(the third vertix being any of the $n$ vertices that is not a vertex of $E$). These triangles either partitions the $(n+2)$-gon into an $(n+1)$-gon and this triangle itself, or a $(k+1)$-gon, $(n+2-k)$-gon and this triangle itself ($2\leq k\leq n-1$). (Perhaps this is easier to see if you draw an $n+2$-gon and label the candidate vertices $1$ through $n$)
Now every triangulation is a refinement of one of these cases, and in each of these cases, the number of possible refinements is the product of the number of triangulations of each component. So $C_n$ for the first case and $C_k \times C_{n+1-k}$ for the second case.
Putting everything together we get \begin{align*} C_{n+1} &= C_n +C_n +\sum_{k=2}^{n-1} C_k \times C_{n+1-k}\\ &= C_1\times C_n + C_n\times C_1 +\sum_{k=2}^{n-1} C_k \times C_{n+1-k}\\ &=\sum_{k=1}^{n} C_k \times C_{n+1-k} \end{align*}