# Recurrence for number of regions formed by diagonals of a convex polygon.

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.

-

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}$.

-

I think you slightly mixed up the indices. You went from an $(n+2)$-gon to an $(n+3)$-gon, whereas the recurrence that goes from $a_{n-1}$ to $a_n$ goes from an $(n+1)$-gon to an $(n+2)$-gon. So let's begin the same way you began, but adding a triangle to an $(n+1)$-gon to create an $(n+2)$-gon. Then as you showed, the triangle contains $n$ new regions.

To each intersection on a diagonal involving the new point there corresponds a new internal edge that increases the number of regions by $1$, namely the edge beginning at that intersection and ending at the next intersection on the diagonal or the endpoint of the diagonal. Now consider all triangles formed by three of the $n+1$ points of the $(n+1)$-gon; there are $\binom{n+1}3$ of these. There are three ways in which we can connect the new point to one of the three points of the triangle and connect the two other points to each other. Of these three, one leads to an intersection and two don't. Also, all pairs of diagonals in which one of the diagonals contains the new point appear exactly once in this count. Thus the number of intersections, and thus of new regions, is $\binom{n+1}3$.

-