# IBHM 509 527 .pdf

Nom original: IBHM_509-527.pdfTitre: IBHM_Ch18v3.qxdAuteur: Claire

Ce document au format PDF 1.6 a été généré par Adobe Acrobat 7.0 / Acrobat Distiller 7.0.5 for Macintosh, et a été envoyé sur fichier-pdf.fr le 07/06/2014 à 21:15, depuis l'adresse IP 87.66.x.x. La présente page de téléchargement du fichier a été vue 603 fois.
Taille du document: 229 Ko (19 pages).
Confidentialité: fichier public

### Aperçu du document

18 Mathematical Induction
Abu Bekr ibn Muhammad ibn al-Husayn Al-Karaji was born on 13 April 953 in
Baghdad, Iraq and died in about 1029. His importance in the field of mathematics is
debated by historians and mathematicians. Some consider that he only reworked
previous ideas, while others see him as the first person to use arithmetic style
operations with algebra as opposed to geometrical operations.
1 1 1
In his work, Al-Fakhri, Al-Karaji succeeded in defining x, x2, x3, p and , 2 , 3 , p
x x x
and gave rules for finding the products of any pair without reference to geometry. He
˛

˛

˛

˛

was close to giving the rule xnxm ⫽ xm⫹n for all integers n and m
˛

˛

˛

˛

but just failed because he did not define x0 ⫽ 1 .
˛

In his discussion and demonstration of this work Al-Karaji used a form of
mathematical induction where he proved a result using the previous result and
noted that this process could continue indefinitely. As we will see in this chapter,
this is not a full proof by induction, but it does highlight one of the major
principles.
Al-Karaji used this form of induction in his work on the binomial theorem,
binomial coefficients and Pascal’s triangle. The table shown is one that Al-Karaji
used, and is actually Pascal’s triangle in its side.
He also worked on the sums of the first n natural numbers, the squares of the first
n natural numbers and the cubes of these
col 1 col 2 col 3 col 4 col 5
numbers, which we introduced in Chapter 6.
1
1
1
1
1
1

2

3

4

5

1

3

6

10

1

4

10

1

5
1

509

18 Mathematical Induction

18.1 Introduction to mathematical
induction
Mathematical induction is a method of mathematical proof. Most proofs presented in
this book are direct proofs – that is proofs where one step leads directly from another to
the required result. However, there are a number of methods of indirect proof including
proof by contradiction, proof by contrapositive and proof by mathematical induction. In
this curriculum, we only consider proof by induction for positive integers.
Mathematical induction is based on the idea of proving the next step to be true if the
previous one is true. If the result is true for an initial value, then it is true for all values.
This is demonstrated by the following metaphor.
Consider a ladder that is infinite in one direction. We want to prove that the ladder is
completely safe, that is each rung on the ladder is sound.

k+1
k

3
2
1

First, test the bottom rung on the ladder and check that it is sound. Then assume that a
rung on the ladder, somewhere further up, is also sound. Call this the kth rung. Using
this assumption, show that the next rung up, the 1k ⫹ 12th rung, is also sound if the
assumption is true. Since we know the first rung is sound, we can now say the second
one is sound. As the second one is sound, the third one is sound and so on. So the

Method for mathematical induction
1.
2.
3.
4.
5.

Prove the result is true for an initial value (normally n ⫽ 1 ).
Assume the result to be true for another value, n ⫽ k, k 7 1, stating this result.
Consider the case for n ⫽ k ⫹ 1, writing down the goal – the required form.
Using the assumption, show that the result is then true for n ⫽ k ⫹ 1.
Communicate why this proves the result using mathematical induction.

Example
n

Prove a r ⫽
r⫽1

n 1n ⫹ 12
∀n H ⺪⫹ by mathematical induction.
2
˛

Remembering the meaning of this notation, we know that ∀ n H ⺪⫹ means that
we need to prove it is true for all positive integers, i.e. n ⱖ 1, n H ⺪.

510

18 Mathematical Induction

1 Prove the result is true for n ⫽ 1.
It is important to show this very clearly (even though it is often obvious).
1

RHS ⫽

LHS ⫽ a r
r⫽1

⫽1

1122
2

⫽1

Since LHS ⫽ RHS, the result is true for n ⫽ 1.
2 Assume the result is true for n ⫽ k, k 7 1, k H ⺪,
k
k 1k ⫹ 12
i.e. a r ⫽
2
r⫽1
˛

3 Now consider the result for n ⫽ k ⫹ 1. We want to show that
k⫹1
1k ⫹ 12 1k ⫹ 1 ⫹ 12
1k ⫹ 12 1k ⫹ 22

ar⫽
2
2
r⫽1
4 For n ⫽ k ⫹ 1,
k⫹1

1k ⫹ 12th term.

k

a r ⫽ a r ⫹ 1k ⫹ 12

r⫽1

r⫽1

k 1k ⫹ 12

⫹ 1k ⫹ 12
2
k 1k ⫹ 12
21k ⫹ 12

2
2
k 1k ⫹ 12 ⫹ 21k ⫹ 12

2
1k ⫹ 12 1k ⫹ 22

2
which is the required form.
˛

We are using the
assumption here.

˛

˛

5 So the result is true for n ⫽ k ⫹ 1 when true for n ⫽ k. Since the result is
true for n ⫽ 1, it is true ∀n H ⺪⫹ by mathematical induction.

This communication is
identical for virtually all
induction proofs. It is
worth learning its form.

Example
n

Prove that

2

a 3r ⫺ 5r ⫽ n 1n ⫹ 12 1n ⫺ 22 ∀n H ⺪
˛

˛

by mathematical

r⫽1

induction.
n

n

We cannot use the standard results for a r and a r2 here as we are being
˛

r⫽1

r⫽1

asked to prove it by mathematical induction.
1 For n ⫽ 1,
1

LHS ⫽ a 3r2 ⫺ 5r
˛

RHS ⫽ 111 ⫹ 12 11 ⫺ 22

r⫽1

⫽ 3112 2 ⫺ 5112

⫽ 1122 1⫺12

⫽3⫺5

⫽ ⫺2

⫽ ⫺2
Since LHS ⫽ RHS, the result is true for n ⫽ 1.

511

18 Mathematical Induction

2 Assume the result to be true for n ⫽ k,
k

i.e. a 3r2 ⫺ 5r ⫽ k 1k ⫹ 12 1k ⫺ 22
˛

˛

r⫽1

3 Consider n ⫽ k ⫹ 1. We want to show that
k⫹1
2
a 3r ⫺ 5r ⫽ 1k ⫹ 12 1k ⫹ 1 ⫹ 12 1k ⫹ 1 ⫺ 22 ⫽ 1k ⫹ 12 1k ⫹ 22 1k ⫺ 12
˛

r⫽1

4 For n ⫽ k ⫹ 1,
k⫹1
2
a 3r ⫺ 5r
˛

r⫽1

1k ⫹ 12th term.

k

⫽ a 13r2 ⫺ 5r2 ⫹ 31k ⫹ 12 2 ⫺ 51k ⫹ 12
˛

r⫽1

⫽ k 1k ⫹ 12 1k ⫺ 22 ⫹ 31k ⫹ 12 2 ⫺ 51k ⫹ 12

We are using the
assumption here.

˛

⫽ 1k ⫹ 12 3k 1k ⫺ 22 ⫹ 31k ⫹ 12 ⫺ 54
˛

⫽ 1k ⫹ 12 3k2 ⫹ k ⫺ 24
˛

⫽ 1k ⫹ 12 1k ⫹ 22 1k ⫺ 12
which is the required form.
5 So the result is true for n ⫽ k ⫹ 1 when true for n ⫽ k. Since the result is
true for n ⫽ 1, it is true ∀n H ⺪⫹ by mathematical induction.

Example
n
1
n
Prove that a

∀n H ⺪⫹ by mathematical induction.
n⫹1
r⫽1 r 1r ⫹ 12
˛

1 For n ⫽ 1,
1
1
LHS ⫽ a
r⫽1 r 1r ⫹ 12

RHS ⫽

˛

1
1122

1
1⫹1
1
2

1
2
Since LHS ⫽ RHS, the result is true for n ⫽ 1.

2 Assume the result to be true for n ⫽ k,
k
1
k
i.e. a

k⫹1
r⫽1 r 1r ⫹ 12
˛

3 Consider n ⫽ k ⫹ 1. We want to show that
1
k⫹1
k⫹1
a r 1r ⫹ 12 ⫽ k ⫹ 1 ⫹ 1 ⫽ k ⫹ 2
r⫽1

k⫹1

˛

512

18 Mathematical Induction

4 For n ⫽ k ⫹ 1,
k⫹1

1
a r 1r ⫹ 12
r⫽1

1k ⫹ 12th term.

˛

k

1
1

⫽ a
1k ⫹ 12 1k ⫹ 22
r⫽1 r 1r ⫹ 12
˛

k
1

k⫹1
1k ⫹ 12 1k ⫹ 22

k 1k ⫹ 22
1

1k ⫹ 12 1k ⫹ 22
1k ⫹ 12 1k ⫹ 22

k2 ⫹ 2k ⫹ 1
1k ⫹ 12 1k ⫹ 22

1k ⫹ 12 2
1k ⫹ 12 1k ⫹ 22

We are using the
assumption here.

˛

˛

k⫹1
k⫹2
which is the required form.

5 So the result is true for n ⫽ k ⫹ 1 when true for n ⫽ k. Since the result
is true for n ⫽ 1, it is true ∀n H ⺪⫹ by mathematical induction.

Example
n
3
Prove that a 3r ⫽ 13n ⫺ 12∀n H ⺪⫹ by mathematical induction.
2
r⫽1

1 For n ⫽ 1,
1

3 1
13 ⫺ 12
2
3
⫽ 122
2
⫽3

LHS ⫽ a 3r

RHS ⫽

r⫽1

⫽ 31
⫽3

Since LHS ⫽ RHS, the result is true for n ⫽ 1.
2 Assume the result to be true for n ⫽ k,
k
3
i.e. a 3r ⫽ 13k ⫺ 12
2
r⫽1
k⫹1
3
3 Consider n ⫽ k ⫹ 1. We want to show that a 3r ⫽ 13k⫹1 ⫺ 12
2
r⫽1
4 For n ⫽ k ⫹ 1,
k⫹1
r

a3

r⫽1

k

⫽ a3 ⫹3
r

k⫹1

1k ⫹ 12th term.

r⫽1

3
⫽ 13k ⫺ 12 ⫹ 3k⫹1
2

Using the
assumption.

513

18 Mathematical Induction

3# k 3
3 ⫺ ⫹ 3.3k
2
2

3
3
⫽ 3k ¢ ⫹ 3≤ ⫺
2
2
9
3
⫽ 3k ¢ ≤ ⫺
2
2

1
19.3k ⫺ 32
2

3
13.3k ⫺ 12
2

3 k⫹1
13
⫺ 12
2

which is the required form.
5 So the result is true for n ⫽ k ⫹ 1 when true for n ⫽ k. Since the result is
true for n ⫽ 1, it is true ∀n H ⺪⫹ by mathematical induction.

It can be seen from these examples that sigma notation is very useful when proving a
result by induction.

Example
Prove that 1.4 ⫹ 2.5 ⫹ 3.6 ⫹ p ⫹ n 1n ⫹ 32 ⫽
˛

1
n 1n ⫹ 12 1n ⫹ 52 ∀n H ⺪⫹.
3
˛

It is simpler to express the LHS using sigma notation. Hence the result becomes
n
1
a r 1r ⫹ 32 ⫽ 3 n 1n ⫹ 12 1n ⫹ 52 .
r⫽1
˛

˛

1 For n ⫽ 1,
1

RHS ⫽

LHS ⫽ a r 1r ⫹ 32
r⫽1

1
122 162
3

= (1)(1 + 3)

⫽4

⫽4

Since LHS ⫽ RHS, the result is true for n ⫽ 1.
2 Assume the result to be true for n ⫽ k,
k
1
i.e. a r 1r ⫹ 32 ⫽ k 1k ⫹ 12 1k ⫹ 52
3
r⫽1
˛

˛

3 Consider n ⫽ k ⫹ 1. We want to show that
k⫹1

1
a r 1r ⫹ 32 ⫽ 3 1k ⫹ 12 1k ⫹ 1 ⫹ 12 1k ⫹ 1 ⫹ 5 2
r⫽1
˛

514

1
112 11 ⫹ 12 11 ⫹ 52
3

1
1k ⫹ 12 1k ⫹ 22 1k ⫹ 6 2
3

18 Mathematical Induction

4 For n ⫽ k ⫹ 1,
k⫹1

a r 1r ⫹ 32
˛

r⫽1

1k ⫹ 12th term.

k

⫽ a r 1r ⫹ 32 ⫹ 1k ⫹ 12 1k ⫹ 42
˛

r⫽1

1
k 1k ⫹ 12 1k ⫹ 52 ⫹ 1k ⫹ 12 1k ⫹ 42
3

1
1k ⫹ 12 3k 1k ⫹ 52 ⫹ 31k ⫹ 42 4
3

1
1k ⫹ 12 3k2 ⫹ 8k ⫹ 124
3

Using the
assumption.

˛

˛

˛

1
1k ⫹ 12 1k ⫹ 22 1k ⫹ 62
3
which is the required form.

5 So the result is true for n ⫽ k ⫹ 1 when true for n ⫽ k. Since the result
is true for n ⫽ 1, it is true ∀n H ⺪⫹ by mathematical induction.

Exercise 1
Prove these results ∀n H ⺪⫹ by mathematical induction.
1

n
1
2
a r ⫽ 6 n 1n ⫹ 12 12n ⫹ 12
r⫽1
˛

n

3

a 3r ⫹ 4 ⫽

r⫽1

5

n

2

˛

n

11
n 13n ⫹ 12
2
˛

n
1
a 8 ⫺ 3r ⫽ 2 n 11 ⫺ 3n2
r⫽1
˛

4

1
a 5r ⫺ 2 ⫽ 2 n 15n ⫹ 12
r⫽1

6

n
4
2
2
a 4r ⫺ 3 ⫽ 3 n 14n ⫹ 6n ⫺ 92
r⫽1

˛

˛

˛

˛

n

2
2
a 6 ⫹ 2r ⫺ r ⫽ 6n 141 ⫹ 3n ⫺ n 2
˛

˛

8

˛

r⫽1
n

9

˛

r⫽1

n

7

2
a 2r ⫺ 1 ⫽ n

3
2
2
a 12r ⫺ 12 ⫽ n 12n ⫺ 12
˛

10

˛

r⫽1

1 2
3
2
a r ⫽ 4 n 1n ⫹ 12
r⫽1
˛

˛

n
1
a r 1r ⫹ 12 ⫽ 3 1n ⫹ 12 1n ⫹ 22
r⫽1
˛

n

11

1
a r 1r ⫹ 12 1r ⫹ 22 ⫽ 4 n 1n ⫹ 12 1n ⫹ 22 1n ⫹ 32
r⫽1
˛

˛

n

12

2
2
a 12r2 ⫽ 3 n 1n ⫹ 12 12n ⫹ 12
r⫽1

13

n
4 n
r
a 4 ⫽ 3 14 ⫺ 12
r⫽1

14

n
n 1n ⫹ 32
1
a r 1r ⫹ 12 1r ⫹ 22 ⫽ 41n ⫹ 12 1n ⫹ 22
r⫽1

˛

˛

˛

n

15

r
1 n

2

¢
≤ 1n ⫹ 22
a r
2
r⫽1 2

16 4 ⫹ 5 ⫹ 6 ⫹p ⫹ 1n ⫹ 32 ⫽

1
n 1n ⫹ 72
2
˛

17 5 ⫹ 3 ⫹ 1 ⫹p ⫹ 17 ⫺ 2n2 ⫽ n 16 ⫺ n2
˛

515

18 Mathematical Induction

18 3 ⫹ 6 ⫹ 11 ⫹ p ⫹ 1n2 ⫹ 22 ⫽
˛

1
n 12n2 ⫹ 3n ⫹ 132
6
˛

19 1.2 ⫹ 2.3 ⫹ 3.4 ⫹ p ⫹ n 1n ⫹ 12 ⫽
˛

˛

1
n 1n ⫹ 12 1n ⫹ 22
3

20 ⫺4 ⫹ 0 ⫹ 6 ⫹ p ⫹ 1n ⫺ 22 1n ⫹ 32 ⫽

˛

1
n 1n2 ⫹ 3n ⫺ 162
3
˛

˛

18.2 Proving some well-known results
So far we have concentrated on proving results that involve sigma notation. However,
mathematical induction can be used to prove results from a variety of mathematical
spheres. These include results from calculus, complex numbers and matrices as well as
algebra.
In earlier chapters, it was stated that proofs would be provided using mathematical
induction for the binomial theorem and de Moivre’s theorem. In this syllabus,
knowledge of the proof of de Moivre’s theorem is expected but not for the binomial
theorem.

Proof of de Moivre’s theorem using mathematical
induction
This was proved in Chapter 17 using calculus, but this method must also be known.
Prove de Moivre’s theorem for all positive integers, i.e.
1cos u ⫹ i sin u2 n ⫽ cos nu ⫹ i sin nu
1 For n ⫽ 1,
LHS ⫽ 1cos u ⫹ i sin u2 1
⫽ cos u ⫹ i sin u

RHS ⫽ cos11u2 ⫹ i sin11u2
⫽ cos u ⫹ i sin u

Since LHS ⫽ RHS, the result is true for n ⫽ 1.
2 Assume the result to be true for n ⫽ k, i.e. 1cos u ⫹ i sin u2 k ⫽ cos ku ⫹ i sin ku
3 Consider n ⫽ k ⫹ 1. We want to show that

Substituting 1k ⫹ 12 for k in
the result.

1cos u ⫹ i sin u2 k⫹1 ⫽ cos1k ⫹ 12 u ⫹ i sin1k ⫹ 12u
We are multiplying the result for
4 For n ⫽ k ⫹ 1,

n ⫽ k by 1cos u ⫹ i sin u 2

1cos u ⫹ i sin u2 k⫹1

to get the result for n ⫽ k ⫹ 1.

⫽ 1cos u ⫹ i sin u2 1cos u ⫹ i sin u2 k
⫽ 1cos u ⫹ i sin u2 1cos ku ⫹ i sin ku2
⫽ cos u cos ku ⫹ i sin ku cos u ⫹ i sin u cos ku ⫹ i2 sin u sin ku
⫽ cos u cos ku ⫺ sin u sin ku ⫹ i 1sin ku cos u ⫹ sin u cos ku2
⫽ cos1u ⫹ ku2 ⫹ i 1sin1ku ⫹ u2 2
⫽ cos1k ⫹ 12u ⫹ i sin1k ⫹ 12 u
which is the required form.
˛

˛

˛

5 So the result is true for n ⫽ k ⫹ 1 when true for n ⫽ k. Since the result is true for
n ⫽ 1, it is true ∀n H ⺪⫹ by mathematical induction.
This can be extended to negative integers by considering n ⫽ ⫺m where m is a positive
integer.

516

Using the assumption.

18 Mathematical Induction

Proof of the binomial theorem for positive integer
powers
n
n
Prove the binomial theorem, i.e. 1x ⫹ y 2 n ⫽ a ¢ ≤ xn⫺ry r.
r⫽0 r
˛

˛

˛

˛

1 For n ⫽ 1,
1
1
RHS ⫽ a ¢ ≤x1⫺ry r
r⫽0 r

LHS ⫽ 1x ⫹ y2 1

˛

˛

˛

1
1
⫽ ¢ ≤x1y 0 ⫹ ¢ ≤x0y1
0
1

⫽x⫹y

˛

˛

˛

˛

˛

˛

⫽x⫹y
Since LHS ⫽ RHS, the result is true for n ⫽ 1.
2 Assume the result to be true for n ⫽ k, i.e.
1x ⫹ y2 k
k
k
k
k
k
k
k
⫽ a ¢ ≤x k⫺ry r ⫽ ¢ ≤x ky 0 ⫹ ¢ ≤x k⫺1y1 ⫹ ¢ ≤x k⫺2y 2 ⫹ p ⫹ ¢ ≤xk⫺ry r ⫹ p ⫹ ¢ ≤x 0y k
0
1
2
r
k
r⫽0 r
˛

˛

˛

˛

˛

˛

˛

˛

˛

˛

˛

˛

˛

˛

˛

˛

˛

˛

k ⫹ 1 k⫹1⫺r r
≤x
y
r

k⫹1

3 Consider n ⫽ k ⫹ 1. We want to show that 1x ⫹ y2 k⫹1 ⫽ a ¢
r⫽0

˛

˛

˛

4 For n ⫽ k ⫹ 1,
1x ⫹ y2 k⫹1
⫽ 1x ⫹ y2 1x ⫹ y2 k
k
k
⫽ 1x ⫹ y2 a ¢ ≤ xk⫺ry r
r⫽0 r
˛

˛

˛

k
k
k
k
k⫺r⫹1 r⫺1
y
⫽ 1x ⫹ y 2B¢ ≤xky 0 ⫹ ¢ ≤x k⫺1y1 ⫹ ¢ ≤x k⫺2y 2 ⫹ p ⫹ ¢r ⫺ 1≤x
0
1
2
˛

˛

˛

˛

˛

˛

˛

˛

˛

˛

˛

˛

k
k
⫹ ¢ ≤xk⫺ryr ⫹ p ⫹ ¢ ≤ x0y kR
r
k
˛

˛

˛

˛

˛

˛

k
k
k
k
k
⫽ ¢ ≤x k⫹1y 0 ⫹ ¢ ≤xky1 ⫹ ¢ ≤x k⫺1y 2 ⫹ p ⫹ ¢
≤xk⫺r ⫹2y r⫺1 ⫹ ¢ ≤xk⫹1⫺ry r
0
1
2
r⫺1
r
˛

˛

˛

˛

˛

˛

˛

˛

˛

˛

˛

˛

˛

˛

˛

k
⫹ p ⫹ ¢ ≤x1yk
k
˛

˛

˛

k
k
k
k
k
⫹ ¢ ≤xky1 ⫹ ¢ ≤xk⫺1y2 ⫹ ¢ ≤xk⫺2y3 ⫹ p ⫹ ¢
≤ xk⫺r⫹1y r ⫹ ¢ ≤xk⫺ry r⫹1
0
1
2
r⫺1
r
˛

˛

˛

˛

˛

˛

˛

˛

˛

˛

˛

˛

˛

˛

˛

k
⫹ p ⫹ ¢ ≤x0yk⫹1
k
˛

˛

˛

k
k
k
k
k
⫽ ¢ ≤xk⫹1 ⫹ B¢ ≤ ⫹ ¢ ≤R xky1 ⫹ B¢ ≤ ⫹ ¢ ≤R xk⫺1y2 ⫹ p
0
1
0
2
1
˛

˛

˛

˛

˛

˛

˛

k
k
k
k
k
⫹ B¢ ≤ ⫹ ¢
≤R xy k ⫹ ¢ ≤y k⫹1
≤R1xk⫹1⫺ry r 2 ⫹ p ⫹ B¢ ≤ ⫹ ¢
r
k
k⫺1
k
r⫺1
˛

˛

˛

˛

˛

517

18 Mathematical Induction

n
n
n⫹1
We can now use the result that ¢ ≤ ⫹ ¢
≤⫽¢
≤ (which was proved in
r
r⫺1
r
Chapter 6).
k
k
So the general term becomes B¢ ≤ ⫹ ¢
≤R1xk⫹1⫺ry r 2
r
r⫺1
˛

˛

˛

k ⫹ 1 k⫹1⫺r r
⫽¢
≤x
y
r
˛

˛

˛

The expansion is therefore
k ⫹ 1 k⫹1
k⫹1 k 1
k ⫹ 1 k⫺1 2
k ⫹ 1 k⫹1⫺r r
¢
≤x
⫹¢
≤x y ⫹ ¢
≤x y ⫹ p ⫹ ¢
≤1x
y 2 ⫹p
0
1
2
r
˛

˛

˛

˛

˛

˛

˛

˛

˛

˛

k⫹1
k ⫹ 1 k⫹1
≤ xy k ⫹ ¢
≤y
k
k⫹1

⫹¢

˛

˛

k ⫹ 1 k⫹1⫺r r
≤x
y
r
r⫽0
which is the required form.
k⫹1

⫽ a¢

˛

˛

˛

5 So the result is true for n ⫽ k ⫹ 1 when true for n ⫽ k. Since the result is true for
n ⫽ 1, it is true ∀n H ⺪⫹ by mathematical induction.
We also use mathematical induction to prove divisibility. This is demonstrated in the
example below.

Example
Prove that 32n ⫹ 7 is divisible by 8 for n H ⺪⫹.
This can be restated as 32n ⫹ 7 ⫽ 8p, p H ⺞.
1 For n ⫽ 1,
32n ⫹ 7 ⫽ 32 ⫹ 7
⫽ 16
As 8 is a factor of 16, or 16 ⫽ 8 ⫻ 2, the result is true for n ⫽ 1.
2 Assume the result to be true for n ⫽ k, i.e. 32k ⫹ 7 ⫽ 8p, p H ⺞.
3 Consider n ⫽ k ⫹ 1. We want to show that 321k⫹12 ⫹ 7 ⫽ 8t, t H ⺞.
4 For n ⫽ k ⫹ 1,
321k⫹12 ⫹ 7 ⫽ 32k⫹2 ⫹ 7
⫽ 3232k ⫹ 7
⫽ 9.32k ⫹ 7
⫽ 9132k ⫹ 7 ⫺ 72 ⫹ 7

This allows us to
use the assumption.

⫽ 918p ⫺ 72 ⫹ 7
⫽ 9.8p ⫺ 63 ⫹ 7
⫽ 9.8p ⫺ 56
⫽ 819p ⫺ 72
Since 19p ⫺ 72 H ⺞, we can say that t ⫽ 9 p ⫺ 7 which is the required
form.
5 So the result is true for n ⫽ k ⫹ 1 when true for n ⫽ k. Since the result is
true for n ⫽ 1, it is true ∀n H ⺪⫹ by mathematical induction.

518

18 Mathematical Induction

There are other algebraic results that we can prove using mathematical induction, as
exemplified below.

Example
Prove that 2n 7 2n ⫹ 1 for all n ⱖ 3, n H ⺞ using mathematical induction.
1 Notice here that the initial value is not n ⫽ 1.
For n ⫽ 3,
LHS ⫽ 23

RHS ⫽ 2132 ⫹ 1

⫽8

⫽7

Since LHS 7 RHS, the result is true for n ⫽ 3.
2 Assume the result to be true for n ⫽ k, k 7 3, i.e. 2k 7 2k ⫹ 1.
3 Consider n ⫽ k ⫹ 1. We want to show that 2k⫹1 7 21k ⫹ 12 ⫹ 1
1 2k⫹1 7 2k ⫹ 3
4 For n ⫽ k ⫹ 1,
2k⫹1 ⫽ 2.2k
7 212k ⫹ 12

Using the assumption.

⫽ 2k ⫹ 2k ⫹ 2
We know that 2k ⫹ 2 7 3, ∀k ⱖ 3 and so 2k ⫹ 2k ⫹ 2 7 2k ⫹ 3
Hence 2k⫹1 7 2k ⫹ 3 which is the required form.
5 So the result is true for n ⫽ k ⫹ 1 when true for n ⫽ k. Since the result
is true for n ⫽ 3, it is true ∀n ⱖ 3, n H ⺞ by mathematical induction.

Induction can also be used to prove results from other spheres of mathematics such as
calculus and matrices.

Example
Prove that

d n
1x 2 ⫽ nxn⫺1, ∀n H ⺪⫹.
dx
˛

˛

1 For n ⫽ 1,
LHS ⫽

d 1
1x 2
dx
˛

⫽1

RHS ⫽ 112x1⫺1
˛

⫽ x0
˛

⫽1
We know the LHS is equal to 1 as the gradient of y ⫽ x is 1. However, we
should prove this by differentiation by first principles as part of a proof.
Let f1x2 ⫽ x
f1x ⫹ h2 ⫺ f1x2 x ⫹ h ⫺ x

h
h
h

h
⫽1

519

18 Mathematical Induction

Hence lim

hS0

f1x ⫹ h2 ⫺ f1x2
⫽1
h

Since LHS ⫽ RHS, the result is true for n ⫽ 1.
2 Assume the result to be true for n ⫽ k, i.e.
d k
1x 2 ⫽ kxk⫺1
dx
˛

˛

3 Consider n ⫽ k ⫹ 1. We want to show that
4 For n ⫽ k ⫹ 1,
d k⫹1
d
1x 2 ⫽
1x.xk 2
dx
dx
˛

d k⫹1
1x 2 ⫽ 1k ⫹ 12xk.
dx
˛

˛

˛

Using the product rule
and the assumption.

⫽ 1.xk ⫹ x.kxk⫺1
˛

˛

⫽ xk ⫹ kxk
˛

˛

⫽ xk 11 ⫹ k2
˛

which is the required form.
5 So the result is true for n ⫽ k ⫹ 1 when true for n ⫽ k. Since the result is
true for n ⫽ 1, it is true ∀n H ⺪⫹ by mathematical induction.

Example
⫺1 n
1
≤ ⫽¢
1
0

1
Prove that ¢
0

⫺n
≤ ∀n H ⺪⫹ using mathematical induction.
1

1 For n ⫽ 1,
1
LHS ⫽ ¢
0
⫽¢

1
0

⫺1 1

1

1
RHS ⫽ ¢
0

⫺1

1

⫺1

1

Since LHS ⫽ RHS, the result is true for n ⫽ 1.
2 Assume the result to be true for n ⫽ k,
1 ⫺1 k
1 ⫺k
≤ ⫽¢

i.e. ¢
0
1
0
1
3 Consider n ⫽ k ⫹ 1. We want to show that
1
¢
0

⫺1 k⫹1
1

⫽¢
1
0

⫺1k ⫹ 12
≤.
1

4 For n ⫽ k ⫹ 1,
1
0

¢

1
⫽¢
0

520

⫺1 k⫹1

1
⫺1 1
≤¢
1
0

⫺1 k

1

18 Mathematical Induction

1
⫽¢
0

⫺1 1
≤¢
1
0

1⫹0
⫽¢
0⫹0
1
⫽¢
0

⫺k

1

Using the assumption.

⫺k ⫺ 1

0⫹1

⫺1k ⫹ 12

1

which is the required form.
5 So the result is true for n ⫽ k ⫹ 1 when true for n ⫽ k. Since the result
is true for n ⫽ 1, it is true ∀n H ⺪⫹ by mathematical induction.

Exercise 2
Prove these results using mathematical induction.
1 Prove that 23n ⫺ 1 is divisible by 7, ∀n H ⺪⫹.
2 Prove that 32n ⫺ 5 is divisible by 4, ∀n H ⺪⫹.
3 Prove that 5n ⫹ 3 is divisible by 4, ∀n H ⺪⫹.
4 Prove that 9n ⫺ 8n ⫺ 1 is divisible by 64, ∀n H ⺪⫹.
5 Prove that 6n ⫹ 4 is divisible by 10, ∀n H ⺪⫹.
6 Prove that n 1n2 ⫺ 12 13n ⫹ 22 is divisible by 24, ∀n H ⺪⫹.
˛

˛

7 Prove that n! 7 2n, for n ⱖ 4, n H ⺪⫹.
8 Prove that n! 7 n2, for n ⱖ 4, n H ⺪⫹.
˛

9 Prove that 2n 7 n3, for n ⱖ 10, n H ⺪⫹.
˛

10 Find the smallest integer t for which n! 7 3n.
Hence prove by induction that n! 7 3n for all n 7 t.
11 For A ⫽ ¢

0
2n
≤, prove that An ⫽ ¢ n
1
2 ⫺1

2
1

12 Prove that

0
≤ ∀n H ⺪⫹.
1

˛

dn px
1e 2 ⫽ pnepx, ∀n H ⺪⫹.
dxn
˛

˛

˛

˛

˛

˛

13 Prove that

1n ⫺ 12p
dn
n⫺1
sin¢2x ⫹
≤, for all positive integer
n 1sin 2x2 ⫽ 2
dx
2
˛

˛

values of n.
1
14 For M ⫽ £0
0

2
p
0

211 ⫺ pn 2
1⫺p
pn
0

1
0
0≥, prove that Mn ⫽ §
0
3
0

˛

˛

˛

0
0
3n

¥, ∀n H ⺪ .

n

4
15 For T ⫽ ¢
0

4n
t
≤, prove that T n ⫽ £
1
0
˛

r⫺1

a4

r⫽1

≥, ∀n H ⺪⫹.

1

521

18 Mathematical Induction

18.3 Forming and proving conjectures
For all of the examples met so far, the result to be proved was given in the question. This
is not always the case; sometimes, it is necessary to form a conjecture which can then be
proved using mathematical induction.

Example
Form a conjecture for the sum

1
1
1
1

⫹ p⫹
.
1⫻2
2⫻3
3⫻4
n 1n ⫹ 12
˛

In order to form the conjecture, consider the results for the first few values of n.
n

1

2

3

4

5

sum

1
2

1
1
2
⫹ ⫽
2
6
3

2
1
3

3
12
4

3
1
4

4
20
5

4
1
5

5
30
6

Looking at the pattern, we can make a conjecture that
1
1
1
1
n

⫹p⫹

1⫻2
2⫻3
3⫻4
n 1n ⫹ 12
n⫹1
˛

We now try to prove this conjecture using mathematical induction.
n
1
.
This can be expressed as a
r
1r

12
r⫽1
˛

1 For n ⫽ 1,
1
1
1
RHS ⫽
LHS ⫽ a
r
1r

12
1

1
r⫽1
1
1

1⫻2
2
1

2
Since LHS ⫽ RHS, the conjecture is true for n ⫽ 1.
˛

2 Assume the result to be true for n ⫽ k,
k
1
k
i.e. a

k⫹1
r⫽1 r 1r ⫹ 12
˛

3 Consider n ⫽ k ⫹ 1. We want to show that
1
k⫹1
k⫹1
a r 1r ⫹ 12 ⫽ k ⫹ 1 ⫹ 1 ⫽ k ⫹ 2 .
r⫽1

k⫹1

˛

4 For n ⫽ k ⫹ 1,
k⫹1

1
a r 1r ⫹ 12

r⫽1

˛

k

1
1
⫽ a

1k ⫹ 12 1k ⫹ 22
r⫽1 r 1r ⫹ 12
k
1

k⫹1
1k ⫹ 12 1k ⫹ 22
k 1k ⫹ 22
1

1k ⫹ 12 1k ⫹ 22
1k ⫹ 12 1k ⫹ 22
˛

˛

522

Using the assumption.

18 Mathematical Induction

k 1k ⫹ 22 ⫹ 1
1k ⫹ 12 1k ⫹ 22

k2 ⫹ 2k ⫹ 1
1k ⫹ 12 1k ⫹ 22

˛

˛

1k ⫹ 12 2
1k ⫹ 12 1k ⫹ 22
k⫹1

k⫹2
which is the required form.

5 So the conjecture is true for n ⫽ k ⫹ 1 when true for n ⫽ k. Since it is
true for n ⫽ 1, it is true ∀ n H ⺪⫹ by mathematical induction.

Example
Form a conjecture for the pentagonal numbers as shown below. Prove your
conjecture by mathematical nduction.

1

5

12

22

So the sequence of pentagonal numbers begins 1, 5, 12, 22, 35, p
Remembering that these are formed by adding “a new layer” each time, we
can consider this as a sum,
1 ⫹ 4 ⫹ 7 ⫹ 10 ⫹ p ⫹ 13n ⫺ 22
We are trying to find a formula for this. This is an arithmetic progression and
so we can apply the formula for the sum to n terms with a ⫽ 1, d ⫽ 3.
Hence Sn ⫽
˛

n
12 ⫹ 31n ⫺ 12 2
2

n
13n ⫺ 12
2

3n2 ⫺ n
2
˛

Again, our conjecture can be expressed using sigma notation:
n

a 3r ⫺ 2 ⫽

r⫽1

3n2 ⫺ n
2
˛

1 For n ⫽ 1,
1

LHS ⫽ a 3r ⫺ 2
r⫽1

⫽3⫺2
⫽1

3112 2 ⫺ 1
2
3⫺1

2
⫽1

RHS ⫽

Since LHS ⫽ RHS, the conjecture is true for n ⫽ 1.

523

18 Mathematical Induction

2 Assume the result to be true for n ⫽ k,
3k2 ⫺ k
2

k

i.e. a 3r ⫺ 2 ⫽

˛

r⫽1

3 Consider n ⫽ k ⫹ 1. We want to show that
k⫹1

a 3r ⫺ 2 ⫽

r⫽1

31k ⫹ 12 2 ⫺ 1k ⫹ 12
2

3k2 ⫹ 6k ⫹ 3 ⫺ k ⫺ 1
2

3k2 ⫹ 5k ⫹ 2
2

˛

˛

4 For n ⫽ k ⫹ 1,
k⫹1

a 3r ⫺ 2

r⫽1

k

⫽ a 3r ⫺ 2 ⫹ 31k ⫹ 12 ⫺ 2
r⫽1

3k2 ⫺ k
⫹ 3k ⫹ 1
2

6k ⫹ 2
3k2 ⫺ k

2
2

3k2 ⫹ 5k ⫹ 2
2

Using the assumption.

˛

˛

˛

which is the required form.
5 So the conjecture is true for n ⫽ k ⫹ 1 when true for n ⫽ k. Since it is
true for n ⫽ 1, it is true ∀n H ⺪⫹ by mathematical induction.

Example
3
For the matrix A ⫽ ¢
0

0
≤, form a conjecture for An, n H ⺪⫹. Prove your
2
˛

conjecture by mathematical induction.
To form the conjecture, find the results for the first few values of n.
A⫽¢

3
0

0

2

9
A2 ⫽ ¢
0

0

4

˛

27
A3 ⫽ ¢
0

0

8

81
A4 ⫽ ¢
0

0

16

˛

˛

3n
From this we can make a conjecture that An ⫽ ¢
0
˛

524

0
≤.
2n

18 Mathematical Induction

We can now prove this using mathematical induction.
1 For n ⫽ 1,
3
0

0 1

2

3
0

0

2

LHS ⫽ ¢

⫽¢

RHS ⫽ ¢

31
0
3
0

⫽¢

0

21
0

2

Since LHS ⫽ RHS, the conjecture is true for n ⫽ 1.
2 Assume the result to be true for n ⫽ k,
i.e. ¢

3
0

3k
0 k
≤ ⫽¢
0
2

0

2k
3
0

3 Consider n ⫽ k ⫹ 1. We want to show that ¢

0 k⫹1
3k⫹1

⫽¢
2
0

0
≤.
2k⫹1

4 For n ⫽ k ⫹ 1,
3
0

¢

0 k⫹1
3
≤ ⫽¢
2
0

0 3
≤¢
2 0

0 k

2

3
0

0 3k
≤¢
2 0

0

2k

⫽¢
⫽¢

˛

˛

3.3k ⫹ 0
0⫹0

⫽¢

3k⫹1
0

Using the assumption.

0⫹0

0 ⫹ 2.2k

0

2k⫹1

which is the required form.
5 So the conjecture is true for n ⫽ k ⫹ 1 when true for n ⫽ k. Since the
conjecture is true for n ⫽ 1, it is true ∀n H ⺪⫹ by mathematical induction.

Exercise 3
1 For the matrix D ⫽ ¢

1
0

1
≤, form a conjecture for Dn. Prove your conjecture
2
˛

using mathematical induction.
2 Form a conjecture for the sum 5 ⫹ 8 ⫹ 11 ⫹ 14 ⫹ p ⫹ 13n ⫹ 22. Prove
3 Form a conjecture for the series suggested by the initial values of
⫺3 ⫹ 1 ⫹ 5 ⫹ 9 ⫹ 13 ⫹ 17 ⫹ p . Prove your conjecture by mathematical
induction.
4 With an unlimited supply of 4p and 7p stamps, make a conjecture about
what values &gt;17 of postage it is possible to create. Prove your conjecture
using mathematical induction.
5 Make a conjecture about the sum of the first n odd numbers. Prove your
conjecture using mathematical induction.

525

18 Mathematical Induction

6 Find an expression for the nth term of the sequence 5, 10, 17, 26, 37, p .
Prove this result to be true using mathematical induction.
7 For the sequence below where each new pattern is made by adding a new
“layer”, make a conjecture for the number of dots in the nth term of the
pattern. Prove this result to be true using mathematical induction.

5

8

13

20

29

Review exercise

M

M–

M+

ON

C

CE

%

X

7

8

9

5

6

÷

2

3

4

1

+

0

M
C

7

4

1

M–

M+

CE

%

8

9

5

6

÷

2

3

+

0

M
C

7

4

1

C

7

4

1

ON
X

M–

M+
%

8

9

5

6

÷

2

3

+

ON
X

=

M–

M+

CE

%

8

9

5

6

÷

2

3

+

0

˛

˛

˛

2 Prove that n5 ⫺ n is divisible by 5, ∀ n H ⺪⫹.
˛

=

CE

0

M

=

n
1
1 Prove that a r 4 ⫽
n 1n ⫹ 12 12n ⫹ 12 13n2 ⫹ 3n ⫺ 12, ∀n H ⺪⫹.
30
r⫽1

ON
X

=

3 Prove that ∀ n H ⺪⫹, 11n⫹1 ⫹ 122n⫺1 is divisible by 133.
4 Prove, using mathematical induction, that
dn
1xepx 2 ⫽ pn⫺1epx 1px ⫹ 12, ∀ n H ⺪⫹.
dxn
˛

˛

˛

˛

˛

M
C

7

4

1

M–

M+

CE

%

8

9

5

6

÷

2

3

+

0

ON
X

=

2
5 Prove, using mathematical induction, that for T ⫽ ¢
p
Tn ⫽ ¢
˛

2n
p 12n ⫺ 12
˛

M
C

7

4

1

M–

M+

CE

%

8

9

5

6

÷

2

3

+

0

ON
X

=

M

M–

M+

C

CE

%

7

8

9

4

5

6

÷

2

3

1

+

0

M
C

7

4

1

ON
X

=

M–

M+

CE

%

8

9

5

6

÷

2

3

+

0

ON
X

=

M

M–

M+

ON

C

CE

%

X

7

8

9

4

5

6

÷

1

2

3

+

0

0
≤,
1

0
≤, ∀ n H ⺪⫹.
1

6 Prove, using mathematical induction, that
12n2!
2 # 6 # 10 # 14 # p # 14n ⫺ 22 ⫽
, ∀ n H ⺪⫹.
n!
7 Prove that sin u ⫹ sin 3u ⫹ p ⫹ sin12n ⫺ 12u ⫽

sin2 nu
, ∀ n H ⺪⫹.
sin u

8 Form a conjecture for the sum 1 ⫻ 1! ⫹ 2 ⫻ 2! ⫹ 3 ⫻ 3! ⫹ p ⫹ n ⫻ n!.
Prove your conjecture by mathematical induction.
9 Using mathematical induction, prove that

=

dn
np
≤, for all
n 1cos x2 ⫽ cos ¢x ⫹
dx
2
˛

˛

˛

positive integer values of n.

[IB May 01 P2 Q4]

Prove using mathematical induction that ¢
✗ 10 a positive
0
integer values of n.
2

M

M–

M+

C

CE

%

7

8

9

4

5

6

÷

1

2

3

+

0

ON
X

=

1 n
2n
≤ ⫽¢
1
0

2n ⫺ 1
≤ for all
1

b Determine whether or not this result is true for n ⫽ ⫺1.
[IB May 02 P2 Q3]

✗ 11 Prove, using mathematical induction, that for a positive integer n,
M
C

7

4

1

M–

M+

CE

%

8

9

5

6

÷

2

3

0

+

ON
X

=

1cos u ⫹ i sin u2 n ⫽ cos nu ⫹ i sin nu where i2 ⫽ ⫺1.
˛

526

[IB May 03 P2 Q3]

18 Mathematical Induction

M

M–

M+

C

CE

%

7

8

9

4

5

6

÷

2

3

1

+

0

ON
X

=

n

12 Using mathematical induction, prove that a 1r ⫹ 122r⫺1 ⫽ n 12n 2 for all
˛

r⫽1

positive integers.

[IB May 05 P2 Q4]

✗ 13 The function f is defined by f1x2 ⫽ e
M
C

7

4

1

M–

M+

CE

%

8

9

5

6

÷

2

3

+

0

ON

px

X

˛

=

˛

1x ⫹ 12,

where p H ⺢.

a Show that f'1x2 ⫽ epx 1p 1x ⫺ 12 ⫹ 12.
˛

˛

b Let f 1n2 1x2 denote the result of differentiating f(x) with respect to x,
˛

n times. Use mathematical induction to prove that
f 1n2 1x2 ⫽ pn⫺1epx 1p 1x ⫹ 12 ⫹ n2, n H ⺪⫹.
˛

M

M–

M+

ON

C

CE

%

X

7

4

1

8

9

5

6

÷

2

3

+

0

=

˛

˛

⫺1
14 For T ⫽ £ 0
0

[IB May 05 P2 Q2]

˛

0
1⫺12 n
n
0≥, prove that T ⫽ £ 0
s
0

3
2
0

˛

2n ⫺ 1⫺12 n
2n
0

using mathematical induction.

0
0 ≥, n H ⺪⫹
sn
˛

[IB May 06 P2 Q5]

✗ 15 Consider the sequence 5a 6, 51, 1, 2, 3, 5, 8, 13, p 6 where a
M
C

7

4

1

M–

M+

CE

%

8

9

5

6

÷

2

3

+

0

ON
X

˛

n

1

˛

⫽ a2 ⫽ 1
˛

=

and an⫹1 ⫽ an ⫹ an⫺1 for all integers n ⱖ 2.
˛

˛

˛

1
1

Given the matrix, Q ⫽ ¢

a
to prove that Qn ⫽ ¢ n⫹1
an
˛

˛

˛

1
≤ use the principle of mathematical induction
0
an

≤ for all integers n ⱖ 2.
an⫺1
˛

˛

[IB Nov 01 P2 Q4]

✗ 16 The matrix M is defined as M ⫽ ¢21
M
C

7

4

1

0

M–

M+

CE

%

8

9

5

6

÷

2

3

+

ON
X

=

⫺1
≤.
0

a Find M2, M3 and M4.
˛

˛

˛

b i State a conjecture for Mn, i.e. express Mn in terms of n, where n H ⺪⫹.
ii Prove this conjecture using mathematical induction.
[IB Nov 02 P2 Q1]
˛

˛

527