Algebra example

Claim: The sum of the first $n$ odd numbers is $n^{2}$ . We will refer to this claim as $P (n)$ .

Try it out

Before proving $P (n)$ with mathematical induction, let’s see if the property holds for some sample values. The sum of the first 3 odd numbers is $1 + 3 + 5 = 9$ . We also have that $3^{2} = 9$ .

The sum of the first 7 odd numbers is $1 + 3 + 5 + 7 + 9 + 11 + 13 = 49$ . We also have that $7^{2} = 49$ .

Another way to express the sum of the first $n$ odd numbers is: $1 + 3 + . . . + (2 n - 1)$ . For example, when $n$ is 4, we have that $2 n - 1 = 7$ . The sum of the first $4$ odd numbers is $1 + 3 + 5 + 7$ .

Induction proof

We wish to use mathematical induction to prove that $P (n)$ holds for all positive integers $n$ That is, that the sum of the first $n$ odd numbers is $n^{2}$ :

\begin{array}{r} 1 + 3 + . . . + (2 n - 1) = n^{2} \end{array}

We will refer to $1 + 3 + . . . + (2 n - 1)$ as $L H S (n)$ and we will refer to $n^{2}$ as $R H S (n)$ . To prove that $P (n)$ holds for some positive integer $n$ , we must prove that $L H S (n) = R H S (n)$ .

Base case

We must prove that $P (n)$ holds for the smallest positive integer, $n = 1$ , that is, that $L H S (1) = R H S (1) .$ The sum the first 1 odd integer is just 1, so we have that $L H S (1) = 1$ . We also have that $R H S (1) = 1^{2} = 1$ .

We have that $L H S (1) = R H S (1)$ . Thus $P (1)$ is true, so the base case holds.

Inductive step

We assume the inductive hypothesis - that $P (k)$ holds for some arbitrary positive integer $k$ . In other words, we assume that $L H S (k) = R H S (k)$ for our arbitrary $k$ . We must prove that $P (k + 1)$ also holds – i.e., that $L H S (k + 1) = R H S (k + 1)$ . We have that:

\begin{matrix} (1) & L H S (k + 1) = 1 + 3 + . . . + (2 k - 1) + (2 (k + 1) - 1) \end{matrix}

\begin{matrix} (2) & = L H S (k) + (2 (k + 1) - 1) \end{matrix}

\begin{matrix} (3) & = R H S (k) + (2 (k + 1) - 1) \end{matrix}

\begin{matrix} (4) & = k^{2} + (2 (k + 1) - 1) \end{matrix}

\begin{matrix} (5) & = k^{2} + 2 k + 2 - 1 \end{matrix}

\begin{matrix} (6) & = k^{2} + 2 k + 1 \end{matrix}

\begin{matrix} (7) & = (k + 1)^{2} \end{matrix}

\begin{matrix} (8) & = R H S (k + 1) \end{matrix}

Thus $L H S (k + 1) = R H S (k + 1)$ , so we have proved $P (k + 1)$ . The inductive step holds.

We conclude that for all positive integers $n$ , $P (n)$ holds – that is, that:

\begin{array}{r} 1 + 3 + . . . + (2 n - 1) = n^{2} \end{array}