# 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

### 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.