Introductory Chapter : Mathematical Logic, Proof and Sets 11

SECTION H Further Mathematical Induction

By the end of this section you will be able to

 apply induction to prove divisibility propositions
 apply induction to prove other mathematical results

In the last section we used the principle of mathematical induction to prove results concerning
finite sums of natural numbers. However this technique of proof can also be used to prove
more widespread results as you will see in this section.
Remember the procedure for proof by mathematical induction of a proposition P  n  is:
1. We check the result for n  1 . Check P 1 .
2. Assume it is true for n  k . Assume P  k  . [Induction hypothesis]
3. Prove the result for n  k  1 by assuming it holds for n  k . Prove
P  k   P  k  1
Remember the procedure for mathematical induction is we check the result is true for n  1
and we assume it is true for any arbitrary number k and then prove it is true for the next
number k  1 . From this we know the result is true for all natural numbers n. Checking P 1
is analogous to the 1st domino being knocked over. Proving P  k   P  k  1 is analogous to
ensuring the kth domino is close enough to the  k  1 th domino to knock it over.
Recall that to prove propositions of the type:
P  n  is true for all natural numbers n
We should first consider ‘proof by induction’.

H1 Divisibility
Remember we can write a divides b by the following notation a b where the vertical line
represents division. Recall a divides b means that there is an integer m such that am  b or
b is a multiple of a . In mathematical notation we write
a b  there is an integer m such that am  b
This was definition (1.5) given earlier in the chapter.
In the next example we prove a result concerning the divisibility of the natural number n 2  n .
In fact we prove n 2  n is an even number.

Example 4
Show that for every natural number n ; n 2  n is divisible by 2, or in notation form
2  n2  n  .
How do we prove the given proposition?
The proposition involves natural numbers n therefore we can try using mathematical
induction. We apply the principle of mathematical induction to show
Introductory Chapter : Mathematical Logic, Proof and Sets 12

2 n 2
 n
That is 2 divides n 2  n exactly, there is NO remainder (or n 2  n is even).
Proof
First we check the proposition is true for n  1 :
12  1  0 √
Clearly 2 divides 0 because 2  0  0 . (Actually every number (apart from 0) divides 0).
Hence the given proposition is true for n  1 .
Next we assume the proposition is true for n  k , that is 2 divides k 2  k . This can be written
in symbolic form as
2 k 2  k 
which means there is an integer m such that
2m  k 2  k (*)
The challenge in applying mathematical induction is to prove the given proposition for the
next number k  1 . What do we need to prove?
We need to show that 2 divides  k  1   k  1 or  k  1   k  1 is a multiple of 2. Well
2 2

let’s examine this expression,  k  1   k  1 , and see if it is a multiple of 2:

2

 k  1   k  1  k 2  2k  1  k  1  Expanding Brackets
2

 k 2  k  2k  1  1  Rearranging 
 k
2
 k  2k
 2 m by (*)

 2m  2k  2  m  k 
Hence  k  1   k  1 is multiple of 2 because
2

 k  1   k  1  2  m  k  [2  (Integer)]
2

Therefore 2 divides  k  1   k  1 . We have proven the given proposition for n  k  1 .

2

Thus by induction, 2 divides n 2  n , our required result.

■
In example 4 we proved that n 2  n is an even number or 2 n 2
 n  . We first checked it was
correct for n  1 then we assumed it was true for n  k and finally we showed the result holds
for n  k  1 - the kth domino knocks over the  k  1 th domino which means all the dominos
have fallen.

Example 5
For every natural number n prove the proposition P  n  given by
3 2 2 n1
 1
What does 3 2 2 n1
 1 mean?
22 n1  1 is divisible by 3 exactly
or there is an integer m such that
Introductory Chapter : Mathematical Logic, Proof and Sets 13

22 n 1  1  3m
That is 22 n1  1 is a multiple of 3 for every natural number n .
Proof
How do we prove 3  22 n1  1 ?
We apply mathematical induction. Why?
Because we need to prove the given proposition P  n  holds for every natural number n .
First we check the proposition is true for n  1 , that is P 1 , by substituting this into 22 n1  1 :
221  1  21  1  3 √
Clearly 3 divides 3 and this is denoted by 3 2 2 1
 1 . Hence the proposition is true for P 1 .
Next we assume the given proposition is true for n  k that is 3 divides 22 k 1  1 . This means
there is an integer q such that
3q  22 k 1  1 (†)
Challenge is to prove the result for the next number k  1 by using (†). How do we write down
P  k  1 ?
By substituting n  k  1 into the given proposition 3 2 2 n1
 1 :
3 2 
2 k 1 1
1 
That is we need to prove
3 divides 22 k 11  1
Let’s examine the right hand term, 22 k 11  1 :
2    1  22 k 1 2  1
2 k 1 1
 Rewriting the index of 2
 22 k 122  1  Applying the rules of indices a m  n  a m a n 
  4  22 k 1  1  Rewriting 22  4 
  3  1 22 k 1  1  Rewriting 4  3  1
  3 22 k 1  22 k 1  1
 Expanding  3  1 22 k 1 
By (†) we know the last two terms on the right hand side , 22 k 1  1 , are equal to 3q .
Therefore we have
22 k 11  1   3 22 k 1  22 k 1
 
1
3 q by  † 

  3 22 k 1  3q
 3  22 k 1  q  Taking out a common factor of 3
Hence the left hand term 22 k 11  1  3  Integer  which means it is a multiple of 3 or 3 divides
 1 . We have proven P  k   P  k  1 . Therefore our result follows by induction.
2 k 1 1
2
■
H2 Using Mathematical Induction to Prove Other Results
Introductory Chapter : Mathematical Logic, Proof and Sets 14

We can apply the principle of mathematical induction to prove general results concerning
natural numbers. For example we can use induction to prove the binomial theorem for positive
integers (natural numbers) which you are asked to show in Exercise 1(h).
There is a great deal of algebraic manipulation in proving the binomial theorem but the
procedure of mathematical induction is the same as in sections G and H1.
Let’s first prove a result regarding the factoring of a n  b n where a and b are real numbers
and n is a natural number. This is a particularly useful result because it can be employed to
factor polynomials of the form a n  b n . The difficulty lies in trying to prove the result for
n  k  1 so we use the ‘trick’ of writing 0 as x  x , or in our Example 6 below
a k b  a k b   0  .
Up to now we have been proving results by mathematical induction for all natural numbers 1,
2, 3, 4,…, n, …
Clearly some results may not be valid for the first few natural numbers. That is the initial
value given in the proposition may not be 1 but some other natural number such as n0 say. In
the next example the result is valid for 1, 2, 3, 4, 5,…, n, … but the starting point is n  2 and
not n  1 . In general the process of mathematical induction is the same apart from the starting
point. If the starting point is n0 then the process of mathematical induction is:
1. We check the result for n  n0 (starting point). Check P  n0  .
2. Assume it is true for n  k . Assume P  k  . [Induction hypothesis]
3. Prove the result for n  k  1 by assuming it holds for n  k . Prove
P  k   P  k  1

Example 6
Let a and b be real numbers then for the natural numbers n  2 we have the proposition
P  n  given by
a n  b n   a  b   a n 1  a n  2b  a n 3b 2    b n 1 
Prove P  n  .
What does this proposition mean?
It says that if you have a polynomial of the form a n  b n then it can be factorized into
 a  b   a n1  a n2b  a n3b2    b n1 
We can use this result to solve equations of the type a n  b n  0 . In any case how do we prove
this result?
It is a result concerning natural numbers n therefore we can use induction.
Proof
We first show this result for n  2 (Our starting point is n  2 ). How?
By substituting n  2 into the given proposition:
a 2  b 2   a  b   a 21  b 21 

 a1  b1

a  b   a  b  a  b 
2 2

Of course this is a fundamental identity in algebra, do you remember what it is called?

Introductory Chapter : Mathematical Logic, Proof and Sets 15

It is the difference of two squares’. Thus P  2  is true.

Assume the proposition is true for n  k that is P  k  . How do we write P  k  ?
By substituting n  k into the given proposition:
a k  b k   a  b   a k 1  a k  2b  a k 3b 2    b k 1  (*)
The difficulty in the process of induction is to prove the result for n  k  1 by employing (*).
What do we need to prove?
Required to prove P  k  1 which is
a k 1  b k 1   a  b   a k 11  a k 1 2b  a k 13b 2    b k 11 
  a  b   a k  a k 1b  a k  2b 2    b k  **
We need to show the left hand side is equal to the right hand side of (**). Let’s consider the
left hand side:
 Using the above stated trick 
a k 1  b k 1  a k 1  a k b  a k b  b k 1  
of writing 0   a b  a b 
k k

 ak a  a k b  a k b  bk b  Using the rules of indices a m  n  a m a n 

 a k  a  b   b  a k  bk   Factorizing out common terms
 a k  a  b   b  a  b   a k 1  a k  2b  a k 3b 2    b k 1 
 
by (*)

=  a  b   a  b  a
k k 1
a k 2
ba b    b k 1  
k 3 2
 Factorizing out  a  b  
 Multiplying by b 
=  a  b   a k  a k 1b  a k  2b 2  a k 3b3    b k  in the second bracket 
 
The last line is the right hand side of (**) so we have shown (**). Hence we have our result,
a n  b n   a  b   a n 1  a n  2b  a n 3b 2    b n 1 
■
Example 6 was a challenging problem but the procedure for mathematical induction remained
the same, apart from the starting point which was n  2 .

H3 Principle of Strong Mathematical Induction

Up to now we have always used an induction hypothesis P  k  to prove the proposition for
the next number, P  k  1 . Sometimes it is difficult to derive P  k  1 from the previous
P  k  . However you may see a connection between P  k  1 and P  m  where m is greater
than or equal to 1 and less than k. Can we use P  m  where 1  m  k to prove P  k  1 ?
Yes of course. Recall the domino effect – all the dominos before the  k  1 th domino have
fallen so the proposition is true for m where 1  m  k . Actually
P 1 , P  2  ,  , P  m  ,  , P  k  are all true
Introductory Chapter : Mathematical Logic, Proof and Sets 16

The difference between strong mathematical induction and just mathematical induction is that
to show P  k  1 we can use any of the previous propositions, that is we can use
P 1 , P  2  ,  , P  m  ,  , P  k 
and not just P  k  .
For the next example we demonstrate a strong induction process.

Example 7
Prove that every integer n  2 is a product of primes.
Proof
Clearly the result holds for n  2 because 2 is a prime.
Assume that result is true for all the natural numbers between 2 and k. This means that the
numbers
2, 3, 4,  , k can be written as a product of primes (*)
We are required to prove that the next number, k  1 , can also be written as a product of
primes.
If k  1 is prime then we are done because we have a product of primes.
If k  1 is composite then there are natural numbers p and q such that
pq  k  1
Note that p and q lie between 2 and k, that is 2  p  k and 2  q  k . By the induction
hypothesis (*) we know that p and q can be written as a product of primes.
Since k  1  pq so we can write k  1 as a product of primes.
By the principle of strong induction we have our result.
■

H4 de Moivre’s Theorem
The following example requires a basic knowledge of complex numbers. If you have not
covered the basic properties of complex numbers then you may find the next example
problematic. However try following it through.
The complex identity we will use is i 2  1 .
This is one of the fundamental theorems of complex numbers called de Moivre’s theorem,
which we will prove by applying mathematical induction.
We prove an important theorem on complex numbers called de Moivre’s theorem by applying
mathematical induction.

Figure 3
Abraham de Moivre
1667 to 1754

Abraham de Movire was born in France in 1667 but moved to England in 1688 because of religious
intolerance in France. He lived in London for the rest of his life, becoming a private tutor in
Introductory Chapter : Mathematical Logic, Proof and Sets 17

mathematics. He wrote a book on probability theory titled ‘Doctrine of Chances’ which was one of
the areas he worked in. He also occupied himself in the fields of trigonometry and algebra.
However, to most undergraduate students he is better known for de Moivre’s theorem, which
converts a complex numbers problem to a trigonometry problem. You can use de Moivre’s
theorem to derive some of the most elegant trigonometric identities.

We need to use the following trigonometric identities to prove de Moivre’s theorem.

cos  A  B   cos  A  cos  B   sin  A  sin  B  † 
sin  A  B   sin  A  cos  B   cos  A  sin  B  †† 
Example 8
Prove de Moivre’s theorem, that is prove that
cos    i sin     cos  n   i sin  n 
n

where n is a natural number.

Proof
Check that the theorem is correct for n  1 :
cos    i sin     cos    i sin  
1
√
Hence the theorem is true for n  1 . Next we assume the theorem is true for n  k , that is
cos    i sin     cos  k   i sin  k 
k
(*)
What is our next step?
We are Required to show that the theorem for the next number, n  k  1 , is true How do we
write down de Moivre’s theorem for n  k  1 ?
By substituting n  k  1 into the given proposition
cos    i sin     cos  n   i sin  n 
n

which gives
cos    i sin     cos   k  1   i sin   k  1 
k 1
(**)
We need to prove (**).
Examining the left hand side of (**) we have
Introductory Chapter : Mathematical Logic, Proof and Sets 18

k 1
 cos    i sin      cos    i sin     cos    i sin   
k 1
 By a m  n  a m a n 
 cos  k   i sin  k    cos    i sin     Remember a1  a 

by (*)

 cos  k  cos    i sin   cos  k  

 Expanding brackets 
 i sin  k  cos     i 2 sin  k  sin   
 cos  k  cos    i sin   cos  k   sin  k  cos     sin  k  sin  
Collecting i terms and using i 2  1
 cos  k  cos    sin  k  sin    i sin   cos  k   cos   sin  k  
   
 cos  k   by  †   sin  k   by  †† 

 Applying the above trigonometric identities

 cos  k     i sin  k    
 cos   k  1    i sin   k  1     Factorizing k     k  1  
The last line is the same as the right hand side of (**). We have established (**), which
means the required result has been proven:
cos    i sin     cos   k  1    i sin   k  1 
k 1

Hence by mathematical induction we have proven de Movire’s theorem for any natural
number n .
■
Comment: de Movire’s theorem is actually true for all real values of n but we have just
proved it for all natural numbers n . In fact de Moivre derived it for natural numbers n but
Euler, the Swiss mathematician, derived it for all real values of n in 1749.

SUMMARY
The general procedure in the case of proving a proposition P  n  by induction is
1. Check the result for P  n0  .
2. Assume it is true for P  k  .
3. Prove P  k   P  k  1 .