PROOF BY INDUCTION

Subtitle

Thuma E. and Zimudzi E.

Department of Computer Science
University of Botswana

03 March, 2025

1 / 20
OUTLINE

1. MATHEMATICAL INDUCTION

2 / 20
Mathematical Induction
To prove that P (n) is true for all positive integers n, where P (n) is a propositional
function, we complete two steps:
BASIS STEP: Verify that P(1) is true.
INDUCTIVE STEP: Show that the conditional statement P (k) → P (k + 1) is true for
all positive integers k.
To complete the inductive step, assume P (k) is true for an arbitrary positive integer k and
show that under this assumption, P (k + 1) must also be true. The assumption that P (k)
is true is called the inductive hypothesis. Once complete both steps, we have shown
that P (n) is true for all positive integers n, that is, we have shown that ∀nP (n) is true
where the quantification is over the set of positive integers. In the inductive step, we show
that ∀k(P (k) → P (k + 1)) is true, where again, the domain is the set of positive integers.
Expressed as a rule of inference, this proof technique can be stated as

(P (1) ∧ ∀k(P (k) → P (k + 1))) → ∀nP (n)

when the domain is the set of positive integers
3 / 20
Template for Proofs by Mathematical Induction
1. Express the statement that is to be proved in the form “for all n ≥ b, P (n)” for a
fixed integer b. For statements of the form “P (n) for all positive integers n,” let
b = 1, and for statements of the form “P (n) for all nonnegative integers n” let
b = 0. For some statements of the form P (n), such as inequalities, you may need to
determine the appropriate value of b by checking the truth values of P (n) for small
values of n.
2. Write out the words “Basis Step.” Then show that P (b) is true, taking care that the
correct value of b is used. This completes the first part of the proof.
3. Write out the words “Inductive Step” and state, and clearly identify, the inductive
hypothesis, in the form “Assume that P (k) is true for an arbitrary fixed integer
k ≥ b.”
4. State what needs to be proved under the assumption that the inductive hypothesis is
true. That is, write out what P (k + 1) says.

4 / 20
5. Prove the statement P (k + 1) making use of the assumption P (k). (Generally, this
is the most difficult part of a mathematical induction proof. Decide on the most
promising proof strategy and look ahead to see how to use the induction hypothesis
to build your proof of the inductive step. Also, be sure that your proof is valid for all
integers k with k ≥ b, taking care that the proof works for small values of k,
including k = b.)
6. Clearly identify the conclusion of the inductive step, such as by saying “This
completes the inductive step.”
7. After completing the basis step and the inductive step, state the conclusion, namely,
“By mathematical induction, P (n) is true for all integers n with n ≥ b.”

5 / 20
Example 1
Show that if n is a positive integer, then
1 + 2 + 3 + · · · + n = n(n+1)
2 .
Solution: Let P(n) be the proposition that the sum of the first n positive integers,
n
1 + 2 + · · · n = n+1 .
We must do two things to prove that P (n) is true for n = 1, 2, 3, · · · . Namely, we must
show that P (1) is true and that the conditional statement P (k) implies P (k + 1) is true
for k = 1, 2, 3, · · · .
BASIS STEP: P (1) is true, because 1 = 1(1+1) 2 . (The left-hand side of this equation is 1
because 1 is the sum of the first positive integer. The right-hand side is found by
substituting 1 for n in n(n+1)
2 .
INDUCTIVE STEP:
For the inductive hypothesis we assume that P (k) holds for an arbitrary positive integer
k. That is, we assume that
1 + 2 + 3 + · · · + k = k(k+1)
2 .

6 / 20
Under this assumption, it must be shown that P(k + 1) is true, namely, that
(k+1)((k+1)+1) (k+1)(k+2)
1 + 2 + 3 + · · · + k + (k + 1) = 2 = 2 , is true.
We add k + 1 to both sides of the equation in P (k), we obtain

k(k + 1)
1 + 2 + 3 + · · · + k + (k + 1) = + (k + 1)
2
k(k + 1) + 2(k + 1)
=
2
(k + 1)(k + 2)
=
2
This last equation shows that P (k + 1) is true under the assumption that P(k) is true.
This completes the inductive step.
By mathematical induction we know that P (n) is true for all positive integers n. That is,
we have proven that
1 + 2 + 3 + · · · + n = n(n+1)
2 for all positive integers n.

7 / 20
Example 2
Show that for all nonnegative integers n,
1 + 2 + 22 + · · · + 2n = 2n+1 − 1.
Solution: Let P(n) be the proposition that
1 + 2 + 22 + · · · + 2n = 2n+1 − 1 for the integer n.
BASIS STEP: P (0) is true, because 20 = 1 = 21 − 1.
INDUCTIVE STEP:
For the inductive hypothesis we assume that P (k) holds for an arbitrary positive integer
k. That is, we assume that
1 + 2 + 22 + · · · + 2k = 2k+1 − 1.
To carry out the inductive step using this assumption, we must show that when we
assume that P (k) is true, then P (k + 1) is also true. We must show that
1 + 2 + 22 + · · · + 2k + 2k+1 = 2k+2 − 1.
assuming the inductive hypothesis P (k). Under the assumption of P(k), we see that

8 / 20
 1 + 2 + 22 + · · · + 2k + 2k+1 = (1 + 2 + 22 + · · · + 2k ) + 2k+1
= 2k+1 − 1 + 2k+1
= 2.2k+1 − 1
= 2k+2 − 1

Because we have completed the basis step and the inductive step, by mathematical
induction we know that P (n) is true for all nonnegative integers n. That is,
1 + 2 + 22 + · · · + 2n = 2n+1 − 1 for all nonnegative integers n.

9 / 20
Example 3
Conjecture a formula for the sum of the first n positive odd integers. Then prove your
conjecture using mathematical induction.
Solution: The sums of the first n positive odd integers for n = 1, 2, 3, 4, 5 are
1=1 1+3=4 1+3+5=9
1 + 3 + 5 + 7 = 16 1 + 3 + 5 + 7 + 9 = 25

10 / 20
From these values it is reasonable to conjecture that the sum of the first n positive odd
integers is n2 , that is,
1 + 3 + 5 + · · · + (2n − 1) = n2 .
We need a method to prove that this conjecture is correct, if in fact it is.
Let P (n) denote the proposition that the sum of the first n odd positive integers is n2 .
Our conjecture is that P (n) is true for all positive integers n. We first complete the basis
step; that is, we must show that P(1) is true.
Then we must carry out the inductive step; i.e. we must show that P (k + 1) is true when
P (k) is assumed to be true.

11 / 20
BASIS STEP: P (1) states that the sum of the first one odd positive integer is 12 . This
is true because the sum of the first odd positive integer is 1. The basis step is complete.
INDUCTIVE STEP: To complete the inductive step we must show that the proposition
P (k) → P (k + 1) is true for every positive integer k. To do this, we first assume the
inductive hypothesis. The inductive hypothesis is the statement that P (k) is true for an
arbitrary positive integer k, that is
1 + 3 + 5 + · · · + 2k − 1 = k 2
To show that ∀k(P (k) → P (k + 1)) is true, we must show that if P (k) is true (the
inductive hypothesis), then P (k + 1) is true. Note that P (k + 1) is the statement that
1 + 3 + 5 + · · · + (2k − 1) + (2k + 1) = (k + 1)2
1 + 3 + 5 + · · · + (2k − 1) + (2k + 1) = 1 + 3 + 5 + · · · + (2k − 1) + (2k + 1)
= k 2 + (2k + 1)
= k 2 + 2k + 1
= (k + 1)2
This shows that P (k + 1) follows from P (k). Note that we used the inductive hypothesis
P (k) in the second equality to replace the sum of the first k odd positive integers by k 2 .
12 / 20
 n
P 1 n
Example 4: Prove by induction that (2i−1)(2i+1) = 2n+1
i=1
1
P 1 1
When n = 1, LHS: (2.1−1)(2.1+1) = 3
i=1
n 1 1
RHS: 2n+1 = 2.1+1 = 3
True when n = 1
k
P 1 k
Assume true for n = k, (2i−1)(2i+1) = 2k+1
i=1
When n = k + 1,

13 / 20
 k+1
X 1
(2i − 1)(2i + 1)
i=1
k
X 1 1
= +
(2i − 1)(2i + 1) (2(k + 1) − 1)(2(k + 1) + 1)
i=1
k 1
= + (1)
2k + 1 (2(k + 1) − 1)(2(k + 1) + 1)
k 1
= +
2k + 1 (2k + 1)(2k + 3)
k(2k + 3) + 1
=
(2k + 1)(2k + 3)
k+1
=
2k + 3
Therefore, it’s true for n = k + 1. Since it’s true for n = 1, it must be true for all n ∈ Z+ .
14 / 20
Example 5- Induction Inequality Proof
Use mathematical induction to prove the inequality n < 2n for all positive integers n.
Solution: Let P (n) be the proposition that n < 2n .
BASIS STEP: P (1) is true, because 1 < 21 = 2
P (1) : 1 < 21
1 < 2 This completes the basis step.
INDUCTIVE STEP: P (k) → P (k + 1)
Inductive hypothesis: k < 2k
Show: k + 1 < 2k+1
k < 2k
k + 1 < 2k + 1 < 2k + 2k = 2.2k
k + 1 < 2k+1

We have completed both the basis step and the inductive step. We have shown that
n < 2n is true for all positive integers n.
15 / 20
Example 6: Prove by mathematical induction that 2n < n! for every integer n ≥ 4
Solution: Let P (n) be the proposition that 2n < n!
BASIS STEP To prove the inequality for n ≥ 4 requires that the basis step be P (4).
Note that P (4) is true, because 24 = 16 < 24 = 4!
INDUCTIVE STEP We assume that P (k) is true for an arbitrary integer k with k ≥ 4.
That is, we assume that 2k < k! for the positive integer k ≥ 4. We must show that under
this hypothesis, P (k + 1) is also true. That is we must show that if 2k < k! for an
arbitrary positive integer k where k ≥ 4.
Show: 2k+1 < (k + 1)!
2k+1 = 2.2k
< 2.k! by the inductive hypothesis
< (k + 1)k! because 2 < k + 1
= (k + 1)! by definition of factorial function
This shows that P (k + 1) is true when P (k) is true.
Hence by mathematical induction, P (n) is true for all integers n with k ≥ 4. That is we
have proved that 2n < n! is true for all integers n with k ≥ 4.
16 / 20
Example 6: Prove that n3 − 7n + 3 is divisible by 3 ∀n ≥ 1.
Solution: Let P (n) be: n3 − 7n + 3 is divisible by 3 ∀n ≥ 1.
Basis Step The basis step is P (1)
P (1) is 13 − 7(1) + 3 = −3, -3 is divisible by 3. So P (1) is true.
Inductive step Assume P (k) is true, P (k) is k 3 − 7k + 3
We show that P (k) → P (k + 1), P (k + 1) is (k + 1)3 − 7(k + 1) + 3 is divisible by 3.
(k + 1)3 − 7(k + 1) + 3 = (k + 1)(k 2 + 2k + 1) − 7(k + 1) + 3
= k 3 + 3k 2 + 3k + 1 − 7k − 7 + 3
= (k 3 − 7k + 3) + 3k 2 + 3k + −6
= (k 3 − 7k + 3) + 3(k 2 + k − 6)
• k 3 − 7k + 3 is divisible by 3 by the inductive hypothesis
• 3(k 2 + k − 6) is divisible by 3
• The sum of 2 integers that are divisible by 3 is also divisible by 3, therefore,
(k 3 − 7k + +3) + 3(k 2 + k − 6) is divisible by 3. Because
(k 3 − 7k + 3) + 3(k 2 + k − 6) is divisible by 3. P (n) is true for all integers n with
k ≥ 1. ∴ n3 − 7n + 3 is divisible by 3 ∀n ≥ 1.
17 / 20
Example 1: Prove that 6n + 4 is divisible by 5 for all positive integers n.
Solution:
Step 1 Prove that the statement is true for n = 1
S1 : 6n + 4 = 61 + 4 = 10. 10 is divisible by 5. So the statement is true for the first term.
Step 2 Assume that the statement is true for n = k
Sk : 6k + 4 = 5m
Sk : 6k = 5m − 4
Step 3 n = k + 1

Sk+1 : 6k+1 + 4

18 / 20
6k .61 + 4 = 6(5m − 4) + 4
= 30m − 24 + 4
= 30m − 20
m is an integer, so 30m − 20 is also an integer
We want the statement 6k+1 + 4 to equal 5L,
i.e. 6k+1 + 4 = 5L
6k+1 + 4 = 5(6m − 4)
6k+1 + 4 = 5L, for L = 6m − 4
As 6k+1 + 4 = 5L. This means the original statement 6n + 4 is divisible by 5 for all
positive integers n.

19 / 20
The End

20 / 20