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