I've been having trouble with this particular problem, been thinking for it for a good hour or two, but I haven't gotten an explanation to the following question.
Suppose $a_n$ be the number of regions into which a convex polygonal region with $n+2$ sides is divided by its diagonals, assuming no three diagonals have a common point. Define $a_0 = 0$. Show that
$a_n = a_{n-1} + {n+1 \choose 3} + n \quad (n \geq 1)$
So far, I have that for $n \geq 1$, we look at an $(n+2)$-gon. Pick an edge from one of the $n+2$ edges from the $(n+2)$-gon. Then adjoin a triangle to it, so we can have an $(n+3)$-gon. Given the triangle that we adjoin to the $(n+2)$-gon, let's look at the exposed vertex of that triangle. We can create $n$ diagonals, since we can't create a diagonal by joining the exposed vertex to an adjacent vertex. So now, we have that $n$ diagonals run through the edge created by the intersection of the $(n+2)$-gon and the triangle. This gives us $n+1$ regions in the triangle. But now, I can't seem to find a pattern to why the $(n+2)$-gon has ${n+1 \choose 3}$ extra regions that is as a result of those $n$ diagonals traversing through the $(n+2)$-gon. Any tip or hint would be appreciated.