Algebra example

Claim: The sum of the first n odd numbers is n2. 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 32=9.

The sum of the first 7 odd numbers is 1+3+5+7+9+11+13=49. We also have that 72=49.

Another way to express the sum of the first n odd numbers is: 1+3+...+(2n1). For example, when n is 4, we have that 2n1=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 n2:

1+3+...+(2n1)=n2

We will refer to 1+3+...+(2n1) as LHS(n) and we will refer to n2 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)=12=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:

(1)LHS(k+1)=1+3+...+(2k1)+(2(k+1)1) (2)=LHS(k)+(2(k+1)1) (3)=RHS(k)+(2(k+1)1) (4)=k2+(2(k+1)1) (5)=k2+2k+21 (6)=k2+2k+1 (7)=(k+1)2 (8)=RHS(k+1)

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:

1+3+...+(2n1)=n2