Geometry Induction

My boss at work gave me this interesting question to work out. It’s unusual as most induction questions are algebraic but this one was related to geometry and counting techniques. Not many of these around. I thought it was pretty cool.

Question

Prove that an \(n\)-sided convex polygon has \(\frac{1}{6}n(n-1)(n-2)\) triangles that can be drawn inside it by connecting any three of the vertices.

Solution

Spoiler

Step 1 (Base Case):

For \(n=3\): \[\frac{1}{6}\times 3\times (3-1) \times (3-2) = 1\]

It is obvious that there is only one triangle to form with three vertices. Hence it is true for the base case of \(n=3\).

(Side note: For \(n<3\) the statement is trivially true as there is no such thing as polygons of less than 3 sides)

Step 2 (Induction Hypothesis):

Assume that it is true for \(n=k\) for some integer \(k\geq 3\). That is,

\(\frac{1}{6}k(k-1)(k-2)\) triangles can be formed between \(k\) number of vertices.

Step 3 (Induction Step):

We are required to prove that the number of triangles possible to be formed for \(n=k+1\) is:

\[\frac{1}{6}(k+1)(k)(k-1)\]

To construct the case for \(n=k+1\), add a vertex between the first and the \(k\)th vertex:

There are two cases when counting the number of triangles that can be formed:

  • Case 1 – When \(x_{k+1}\) is not a vertex of the triangles. The number of triangles that can be formed in the polygon defined by \(x_1x_2x_3\ldots x_k\) is simply the induction hypothesis as there are \(k\) vertices. That is, in Case 1 the number of triangles possible is:
    \[\frac{1}{6}k(k-1)(k-2)\]
  • Case 2 – When \(x_{k+1}\) is a vertex of the triangles. There then remains 2 vertices to be chosen from the other \(k\) vertices to form a triangle. Therefore, the number of triangles possible in Case 2 is:
    \[\left(\matrix{k\\2}\right)=\frac{k!}{(k-2)!2!}=\frac{k(k-1)}{2}\]

Hence, the number of triangles formed for \(k+1\) vertices is found by adding Case 1 and Case 2 together:

\[\begin{align*}&\frac{1}{6}k(k-1)(k-2)+\frac{k(k-1)}{2}\\=&\frac{1}{6}k(k-1)(k-2+3)\\=&\frac{1}{6}k(k-1)(k-+1)\\=&\frac{1}{6}(k+1)(k)(k-1)\end{align*}\]

Therefore the statement is true for \(n=k+1\).

By the principle of mathematical induction, it is therefore true for integers \(n\geq 3\) that \(\frac{1}{6}n(n-1)(n-2)\) triangles can be formed from a convex polygon of \(n\) vertices.

[collapse]

Add a Comment

Your email address will not be published. Required fields are marked *