Correct solutions were received from Paul Botham, Philippe Fondanaiche, Juan Carlos Marivela, Al Zimmermann, and the proposer, Nancy Schwarzkopf.

Let r_n be the number of regions in a subdivided n-gon.  Label the vertices of an (n+1)-gon, P, consecutively 1,2,...,n+1. The n-gon formed by the vertices 1,...,n, say Q, and its diagonals form r_n regions.  When we draw in the n-2 diagonals from the vertex labeled n+1 we create n-1 new regions in the triangle with vertices 1,n,n+1.   

Next, a diagonal joining n+1 to j, for 1 < j < n, cuts some of the regions in Q into two pieces.  See the figure on the left.  Look at the first edge the diagonal crosses, coloured blue in the figure, as it enters one of those regions.  This edge is determined by two vertices i,j with 1 £ i < j £ n; conversely, any such pair of vertices determines such an edge and a corresponding region in Q.  The number of such triples is .  This gives the recursion relation  r_n = r_n + + n-1, r₄ = 4.  Resorting to a complicated argument with generating function or a simple argument with induction gives the final result

r_n = .

You are visitor number  3694 to this page.