Algebra example
Claim: The sum of the first
odd numbers is
. We will refer to this claim as
.
Try it out
Before proving
with mathematical induction, let’s see if the property holds for some sample values. The sum of the first 3 odd numbers is
. We also have that
.
The sum of the first 7 odd numbers is
. We also have that
.
Another way to express the sum of the first
odd numbers is:
. For example, when
is 4, we have that
. The sum of the first
odd numbers is
.
Induction proof
We wish to use mathematical induction to prove that
holds for all positive integers
That is, that the sum of the first
odd numbers is
:
We will refer to
as
and we will refer to
as
. To prove that
holds for some positive integer
, we must prove that
.
Base case
We must prove that
holds for the smallest positive integer,
, that is, that
The sum the first 1 odd integer is just 1, so we have that
. We also have that
.
We have that
. Thus
is true, so the base case holds.
Inductive step
We assume the inductive hypothesis - that
holds for some arbitrary positive integer
. In other words, we assume that
for our arbitrary
. We must prove that
also holds – i.e., that
. We have that:
Thus
, so we have proved
. The inductive step holds.
We conclude that for all positive integers
,
holds – that is, that: