Why is Segner's Recurrence Relation formula valid. Does anyone know how to prove it?
I can't seem to understand why this formula works/is true.
$$C_0 = 1,\quad C_{n+1} = C_0C_n + C_1C_{n−1}+ \cdots + C_kC_{n−k} + \cdots + C_nC_0\text{ ?}$$
Where Cn 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 looked it up. The formula, according to mathworld, is $ E_n=E_2E_{n-1}+E_3E_{n-2}+...+E_{n-1}E_2 $, where $E_n$ is the number of ways of dividing a polygon by diagonals.
The way I look at this, is that each of the terms ($E_k E_{n-k+1}$) represents a division of the polygon into two subpolygons by a single diagonal.
The two terms in the product represent the number of ways each subpolygon can, in turn, be divided by diagonals.
I know this is moderately hand-wavey, but it's my way of understanding the formula.