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 + ... + (2n - 1)$. For example, when $n$ is 4, we have that $2n - 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{aligned} 1 + 3 + ... + (2n - 1) = n^2 \end{aligned} $$

We will refer to $1 + 3 + ... + (2n - 1)$ as $LHS(n)$ and we will refer to $n^2$ as $RHS(n)$. To prove that $P(n)$ holds for some positive integer $n$, we must prove that $LHS(n) = RHS(n)$.

Base case

We must prove that $P(n)$ holds for the smallest positive integer, $n = 1$, that is, that $LHS(1) = RHS(1). $ The sum the first 1 odd integer is just 1, so we have that $LHS(1) = 1$. We also have that $RHS(1) = 1^2 = 1$.

We have that $LHS(1) = RHS(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 $LHS(k) = RHS(k)$ for our arbitrary $k$. We must prove that $P(k+1)$ also holds – i.e., that $LHS(k+1) = RHS(k+1)$. We have that:

$$ LHS(k+1) = 1 + 3 + ... + (2k - 1) + (2(k + 1) - 1) \tag{1} $$ $$ = LHS(k) + (2(k + 1) - 1) \tag{2} $$ $$ = RHS(k) + (2(k + 1) - 1) \tag{3} $$ $$ = k^2 + (2(k + 1) - 1) \tag{4} $$ $$ = k^2 + 2k + 2 - 1 \tag{5} $$ $$ = k^2 + 2k + 1 \tag{6} $$ $$ = (k+1)^2 \tag{7} $$ $$ = RHS(k+1) \tag{8} $$

Thus $LHS(k+1) = RHS(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{aligned} 1 + 3 + ... + (2n - 1) = n^2 \end{aligned} $$