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.
Best Answer
Well, since your recurrence defines $a_n$ in terms of $a_{n-1}$, I think it would be more appropriate to consider the additional regions created when adding the $(n+2)$nd vertex to an $(n+1)$-gon rather than the $(n+3)$rd vertex to an $(n+2)$-gon.
So, suppose we have an $(n+2)$-gon. Designate the "exposed vertex" $X$, and call the other vertices $P_1$, $P_2$, ..., $P_{n+1}$, where $P_1$ and $P_{n+1}$ are adjacent to $X$. The $P_i$s form an $(n+1)$-gon within which there are $a_{n-1}$ regions made from all the diagonals and sides $P_iP_j$. Now consider the $n-1$ diagonals emanating from $X$ and finishing at $P_k$, where $2 \leq k \leq n$. As we draw these, whenever a diagonal hits a previously drawn diagonal, it enters a different region, which will be cut into two regions when the diagonal hits the next line. That is, for every intersection between a new diagonal $XP_k$ and an old diagonal $P_iP_j$, we make one new region inside polygon $P_1\ldots P_{n+1}$. How many such intersections are there? It's just the number of ways to pick three integers $1 \leq i < k < j \leq n+1$, that is, $\binom{n+1}3$.
And then of course we have the $n$ new regions inside the triangle $XP_1P_{n+1}$.