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