MATENA1:
Mathematical Induction
Section 2.2
Mathematical Induction:
Let S be a set of natural numbers and let
a be a natural number. If the following
are true
(1) a ∈ S
(2) k ∈ S =⇒ k + 1 ∈ S
then S contains every natural number
greater than or equal to a.
If we think about it, mathematical induction
makes intuitive sense. Let’s assume
statements (1) and (2) and consider the
following sequence of deductions.
If we think about it, mathematical induction
makes intuitive sense. Let’s assume
statements (1) and (2) and consider the
following sequence of deductions.
From (1) we deduce that a ∈ S.
If we think about it, mathematical induction
makes intuitive sense. Let’s assume
statements (1) and (2) and consider the
following sequence of deductions.
From (1) we deduce that a ∈ S.
From the statement above and (2) we
deduce that a + 1 ∈ S.
If we think about it, mathematical induction
makes intuitive sense. Let’s assume
statements (1) and (2) and consider the
following sequence of deductions.
From (1) we deduce that a ∈ S.
From the statement above and (2) we
deduce that a + 1 ∈ S.
From the statement above and (2) we
deduce that a + 2 ∈ S.
From the statement above and (2) we
deduce that a + 3 ∈ S.
From the statement above and (2) we
deduce that a + 3 ∈ S.
From the statement above and (2) we
deduce that a + 4 ∈ S.
From the statement above and (2) we
deduce that a + 3 ∈ S.
From the statement above and (2) we
deduce that a + 4 ∈ S.
Etc...
From the statement above and (2) we
deduce that a + 3 ∈ S.
From the statement above and (2) we
deduce that a + 4 ∈ S.
Etc...
We see that if we continue in this way, S will
have to contain each of a, a + 1, a + 2, . . ..
From the statement above and (2) we
deduce that a + 3 ∈ S.
From the statement above and (2) we
deduce that a + 4 ∈ S.
Etc...
We see that if we continue in this way, S will
have to contain each of a, a + 1, a + 2, . . ..
Let’s see how we can use mathematical
induction to solve problems...
Example: Use mathematical induction to
n(n + 1)
show that 1 + 2 + · · · + n = for
2
each natural number n ≥ 1.
Example: Use mathematical induction to
n(n + 1)
show that 1 + 2 + · · · + n = for
2
each natural number n ≥ 1.
Solution: Let S be the set of all natural
numbers n ≥ 1 for which
n(n + 1)
1 + 2 + ··· + n = .
2
Example: Use mathematical induction to
n(n + 1)
show that 1 + 2 + · · · + n = for
2
each natural number n ≥ 1.
Solution: Let S be the set of all natural
numbers n ≥ 1 for which
n(n + 1)
1 + 2 + ··· + n = .
2
We will use mathematical induction to show
that S contains all natural numbers greater
than or equal to 1.
Solution continued. . .
We first show that 1 ∈ S.
Solution continued. . .
We first show that 1 ∈ S. If n = 1, then
1(1 + 1)
LHS = 1 and RHS = = 1.
2
Solution continued. . .
We first show that 1 ∈ S. If n = 1, then
1(1 + 1)
LHS = 1 and RHS = = 1.
2
So, when n = 1 it follows that LHS = RHS
and hence that 1 ∈ S.
Solution continued. . .
Assume that k ∈ S (this assumption is called
the induction hypothesis).
Solution continued. . .
Assume that k ∈ S (this assumption is called
the induction hypothesis). That is,
k(k + 1)
1 + 2 + 3 + ··· + k = .
2
Solution continued. . .
Assume that k ∈ S (this assumption is called
the induction hypothesis). That is,
k(k + 1)
1 + 2 + 3 + ··· + k = .
2
Now we verify that the equation holds for the
case where n = k + 1,
Solution continued. . .
Assume that k ∈ S (this assumption is called
the induction hypothesis). That is,
k(k + 1)
1 + 2 + 3 + ··· + k = .
2
Now we verify that the equation holds for the
case where n = k + 1, that is, we will show
that:
(k + 1)(k + 1 + 1)
1+2+3+· · ·+k+(k+1) =
2
Solution continued. . .
Consider the left-hand side of the last equation on
the previous slide:
LHS = 1| + 2 + 3{z
+ . . . + k} + (k + 1)
Solution continued. . .
Consider the left-hand side of the last equation on
the previous slide:
LHS = 1| + 2 + 3{z
+ . . . + k} + (k + 1)
k(k + 1)
= + (k + 1) (by inductive hypothesis)
2
Solution continued. . .
Consider the left-hand side of the last equation on
the previous slide:
LHS = 1| + 2 + 3{z
+ . . . + k} + (k + 1)
k(k + 1)
= + (k + 1) (by inductive hypothesis)
2
k(k + 1) + 2(k + 1)
=
2
Solution continued. . .
Consider the left-hand side of the last equation on
the previous slide:
LHS = 1| + 2 + 3{z
+ . . . + k} + (k + 1)
k(k + 1)
= + (k + 1) (by inductive hypothesis)
2
k(k + 1) + 2(k + 1)
=
2
2
k + k + 2k + 2
=
2
Solution continued. . .
Consider the left-hand side of the last equation on
the previous slide:
LHS = 1| + 2 + 3{z
+ . . . + k} + (k + 1)
k(k + 1)
= + (k + 1) (by inductive hypothesis)
2
k(k + 1) + 2(k + 1)
=
2
2
k + k + 2k + 2
=
2
2
k + 3k + 2
=
2
Solution continued. . .
k 2 + 3k + 2
LHS =
2
Solution continued. . .
k 2 + 3k + 2
LHS =
2
(k + 1)(k + 2)
=
2
Solution continued. . .
k 2 + 3k + 2
LHS =
2
(k + 1)(k + 2)
=
2
(k + 1)((k + 1) + 1)
= = RHS
2
Solution continued. . .
k 2 + 3k + 2
LHS =
2
(k + 1)(k + 2)
=
2
(k + 1)((k + 1) + 1)
= = RHS
2
Therefore, k + 1 ∈ S,
Solution continued. . .
k 2 + 3k + 2
LHS =
2
(k + 1)(k + 2)
=
2
(k + 1)((k + 1) + 1)
= = RHS
2
Therefore, k + 1 ∈ S, and hence, by Mathematical
Induction, S contains all natural numbers n ≥ 1.
Solution continued. . .
k 2 + 3k + 2
LHS =
2
(k + 1)(k + 2)
=
2
(k + 1)((k + 1) + 1)
= = RHS
2
Therefore, k + 1 ∈ S, and hence, by Mathematical
Induction, S contains all natural numbers n ≥ 1.
Therefore,
n(n + 1)
1 + 2 + 3 + ··· + n =
2
for all natural numbers n > 1.
Solution continued. . .
k 2 + 3k + 2
LHS =
2
(k + 1)(k + 2)
=
2
(k + 1)((k + 1) + 1)
= = RHS
2
Therefore, k + 1 ∈ S, and hence, by Mathematical
Induction, S contains all natural numbers n ≥ 1.
Therefore,
n(n + 1)
1 + 2 + 3 + ··· + n =
2
for all natural numbers n > 1.
Example: Use mathematical induction to
2 n 3n+1 − 1
show that 1 + 3 + 3 + · · · + 3 =
2
for each natural number n ≥ 0.
Example: Use mathematical induction to
2 n 3n+1 − 1
show that 1 + 3 + 3 + · · · + 3 =
2
for each natural number n ≥ 0.
Solution: Let S be the set of all natural
numbers n ≥ 0 for which
2 n3n+1 − 1
1 + 3 + 3 + ··· + 3 = .
2
Example: Use mathematical induction to
2 n 3n+1 − 1
show that 1 + 3 + 3 + · · · + 3 =
2
for each natural number n ≥ 0.
Solution: Let S be the set of all natural
numbers n ≥ 0 for which
2 n3n+1 − 1
1 + 3 + 3 + ··· + 3 = .
2
We will use mathematical induction to show
that S contains all natural numbers greater
than or equal to 0.
Solution continued. . .
We first show that 0 ∈ S.
Solution continued. . .
We first show that 0 ∈ S. If n = 0, then
30+1 − 1
LHS = 1 and RHS = = 1.
2
Solution continued. . .
We first show that 0 ∈ S. If n = 0, then
30+1 − 1
LHS = 1 and RHS = = 1.
2
So, when n = 0 it follows that LHS = RHS
and hence that 0 ∈ S.
Solution continued. . .
Assume that k ∈ S (this is the induction
hypothesis).
Solution continued. . .
Assume that k ∈ S (this is the induction
hypothesis). That is,
3k+1 − 1
k
1 + 3 + ··· + 3 = .
2
Solution continued. . .
Assume that k ∈ S (this is the induction
hypothesis). That is,
3k+1 − 1
k
1 + 3 + ··· + 3 = .
2
Now we verify that the equation holds for the
case where n = k + 1,
Solution continued. . .
Assume that k ∈ S (this is the induction
hypothesis). That is,
3k+1 − 1
k
1 + 3 + ··· + 3 = .
2
Now we verify that the equation holds for the
case where n = k + 1, that is, we will show
that:
k k+1 3(k+1)+1 − 1
1 + 3 + ··· + 3 + 3 = .
2
Solution continued. . .
Consider the left-hand side of the last equation on
the previous slide:
LHS = 1 + 3 + · · · + 3k + 3k+1
Solution continued. . .
Consider the left-hand side of the last equation on
the previous slide:
LHS = 1 + 3 + · · · + 3k + 3k+1
3k+1 − 1
= + 3k+1 (by induction hypothesis)
2
Solution continued. . .
Consider the left-hand side of the last equation on
the previous slide:
LHS = 1 + 3 + · · · + 3k + 3k+1
3k+1 − 1
= + 3k+1 (by induction hypothesis)
2
k+1
3 + 2(3k+1 ) − 1
=
2
Solution continued. . .
Consider the left-hand side of the last equation on
the previous slide:
LHS = 1 + 3 + · · · + 3k + 3k+1
3k+1 − 1
= + 3k+1 (by induction hypothesis)
2
k+1
3 + 2(3k+1 ) − 1
=
2
k+1
3 (1 + 2) − 1
=
2
Solution continued. . .
Consider the left-hand side of the last equation on
the previous slide:
LHS = 1 + 3 + · · · + 3k + 3k+1
3k+1 − 1
= + 3k+1 (by induction hypothesis)
2
k+1
3 + 2(3k+1 ) − 1
=
2
k+1
3 (1 + 2) − 1
=
2
k+1
3 (3) − 1
=
2
Solution continued. . .
3k+2 − 1
LHS =
2
Solution continued. . .
3k+2 − 1
LHS =
2
(k+1)+1
3 −1
= = RHS
2
Solution continued. . .
3k+2 − 1
LHS =
2
(k+1)+1
3 −1
= = RHS
2
From this it follows that k + 1 ∈ S.
Solution continued. . .
3k+2 − 1
LHS =
2
(k+1)+1
3 −1
= = RHS
2
From this it follows that k + 1 ∈ S. By
Mathematical Induction we conclude that S
contains every natural number greater than or equal
to 0.
Solution continued. . .
3k+2 − 1
LHS =
2
(k+1)+1
3 −1
= = RHS
2
From this it follows that k + 1 ∈ S. By
Mathematical Induction we conclude that S
contains every natural number greater than or equal
to 0. Therefore, for any natural number n ≥ 0,
n ∈ S and hence (recalling the definition of S)
n 3n+1 − 1
1 + 3 + ··· + 3 = .
2
Example: Use mathematical induction to
show that 4n − 1 is divisible by 3 for every
natural number n ≥ 0.
Example: Use mathematical induction to
show that 4n − 1 is divisible by 3 for every
natural number n ≥ 0.
Solution: Let S be the set of all natural
numbers n ≥ 0 for which 4n − 1 is divisible
by 3.
Example: Use mathematical induction to
show that 4n − 1 is divisible by 3 for every
natural number n ≥ 0.
Solution: Let S be the set of all natural
numbers n ≥ 0 for which 4n − 1 is divisible
by 3. We will use mathematical induction to
show that S contains all natural numbers
greater than or equal to 0.
Solution continued. . .
We first show that 0 ∈ S.
Solution continued. . .
We first show that 0 ∈ S. If n = 0, then
40 − 1 = 1 − 1 = 0.
Solution continued. . .
We first show that 0 ∈ S. If n = 0, then
40 − 1 = 1 − 1 = 0. Now, 3 divides 0 since
0 = 3(0).
Solution continued. . .
We first show that 0 ∈ S. If n = 0, then
40 − 1 = 1 − 1 = 0. Now, 3 divides 0 since
0 = 3(0). So 0 ∈ S.
Solution continued. . .
We first show that 0 ∈ S. If n = 0, then
40 − 1 = 1 − 1 = 0. Now, 3 divides 0 since
0 = 3(0). So 0 ∈ S.
Assume that k ∈ S (this is the induction
hypothesis).
Solution continued. . .
We first show that 0 ∈ S. If n = 0, then
40 − 1 = 1 − 1 = 0. Now, 3 divides 0 since
0 = 3(0). So 0 ∈ S.
Assume that k ∈ S (this is the induction
hypothesis). We will now show that
k + 1 ∈ S.
Solution continued. . .
We first show that 0 ∈ S. If n = 0, then
40 − 1 = 1 − 1 = 0. Now, 3 divides 0 since
0 = 3(0). So 0 ∈ S.
Assume that k ∈ S (this is the induction
hypothesis). We will now show that
k + 1 ∈ S. Since k ∈ S it follows that 4k − 1
is divisible by 3.
Solution continued. . .
We first show that 0 ∈ S. If n = 0, then
40 − 1 = 1 − 1 = 0. Now, 3 divides 0 since
0 = 3(0). So 0 ∈ S.
Assume that k ∈ S (this is the induction
hypothesis). We will now show that
k + 1 ∈ S. Since k ∈ S it follows that 4k − 1
is divisible by 3. That is, there exists m ∈ Z
such that 4k − 1 = 3m,
Solution continued. . .
We first show that 0 ∈ S. If n = 0, then
40 − 1 = 1 − 1 = 0. Now, 3 divides 0 since
0 = 3(0). So 0 ∈ S.
Assume that k ∈ S (this is the induction
hypothesis). We will now show that
k + 1 ∈ S. Since k ∈ S it follows that 4k − 1
is divisible by 3. That is, there exists m ∈ Z
such that 4k − 1 = 3m, so 4k = 3m + 1.
Solution continued. . .
Therefore,
4k+1 − 1 = 4(4k ) − 1
Solution continued. . .
Therefore,
4k+1 − 1 = 4(4k ) − 1
= 4(3m + 1) − 1
Solution continued. . .
Therefore,
4k+1 − 1 = 4(4k ) − 1
= 4(3m + 1) − 1
= 12m + 4 − 1
Solution continued. . .
Therefore,
4k+1 − 1 = 4(4k ) − 1
= 4(3m + 1) − 1
= 12m + 4 − 1
= 12m + 3
Solution continued. . .
Therefore,
4k+1 − 1 = 4(4k ) − 1
= 4(3m + 1) − 1
= 12m + 4 − 1
= 12m + 3
= 3(4m + 1)
Solution continued. . .
Therefore,
4k+1 − 1 = 4(4k ) − 1
= 4(3m + 1) − 1
= 12m + 4 − 1
= 12m + 3
= 3(4m + 1)
Since m is an integer, so is 4m + 1.
Solution continued. . .
Therefore,
4k+1 − 1 = 4(4k ) − 1
= 4(3m + 1) − 1
= 12m + 4 − 1
= 12m + 3
= 3(4m + 1)
Since m is an integer, so is 4m + 1. Hence,
3 divides 4k+1 − 1.
Solution continued. . .
Therefore,
4k+1 − 1 = 4(4k ) − 1
= 4(3m + 1) − 1
= 12m + 4 − 1
= 12m + 3
= 3(4m + 1)
Since m is an integer, so is 4m + 1. Hence,
3 divides 4k+1 − 1. We now conclude that
k + 1 ∈ S.
Solution continued. . .
By mathematical induction it follows that S
contains every natural number greater than
or equal to 0.
Solution continued. . .
By mathematical induction it follows that S
contains every natural number greater than
or equal to 0. Therefore, for any natural
number n ≥ 0, n ∈ S and hence (recalling
the definition of S) 4n − 1 is divisible by 3.
Solution continued. . .
By mathematical induction it follows that S
contains every natural number greater than
or equal to 0. Therefore, for any natural
number n ≥ 0, n ∈ S and hence (recalling
the definition of S) 4n − 1 is divisible by 3.
In the previous example, when showing that
4k+1 − 1 is divisible by 3 we made use of the
fact that 4k − 1 is divisible by 3.
In the previous example, when showing that
4k+1 − 1 is divisible by 3 we made use of the
fact that 4k − 1 is divisible by 3.
The fact that 4k − 1 is divisible by 3 followed
from the induction hypothesis.
In the previous example, when showing that
4k+1 − 1 is divisible by 3 we made use of the
fact that 4k − 1 is divisible by 3.
The fact that 4k − 1 is divisible by 3 followed
from the induction hypothesis.
When solving an induction problem, please
ensure that you make use of the induction
hypothesis. If you don’t use the induction
hypothesis, that is how you know that you’ve
done something incorrect.
Prescribed tut problems
I Section 2.2:
1, 2, 3, 4, 5, 7, 8, 10 (if you want to
challenge yourself)
