Mathematical Induction

Compiled by: Nyasha P. Tarakino (Trockers)

+263772978155/+263717267175

ntarakino@gmail.com

21 February 2019

Tarakino N.P. (Trockers) ~ 0772978155/ 0717267175

Page 1
 SYLLABUS (6042) REQUIREMENTS

 describe the process of mathematical induction
 prove by mathematical induction to establish a given
result
 use the strategy of conducting limited trials to
formulate a conjecture and proving it by the method
of induction










Tarakino N.P. (Trockers) ~ 0772978155/ 0717267175

Page 2
 MATHEMATICAL INDUCTION

NOTES

Definition: It is a method of proof in which a statement is proved for one step in a process,
and it is shown that if the statement holds for that step, it holds for the next.

STEPS

i. Base Case/Initial Stage

Show it is true for and give a conclusion for this stage.
ii. Assumption/Hypothesis Stage
Suppose/ assume the statement is true for .
iii. Thesis Stage
Stating the result for
iv. Proof Stage
Proving true for . Use the thesis stage and the hypothesis stage to get the
required result. Give a conclusion for this stage.
v. Conclusion Stage
State four conditions clearly:

Areas to consider

 Divisibility
 Series/Summations
 Matrices
 Integration
 Differentiation
 Factorial Notation
 Composite Functions
 Binomial etc

Tarakino N.P. (Trockers) ~ 0772978155/ 0717267175

Page 3
 DIVISIBILITY
DIVISIBILITY

DIVISIBILITY
Examples

1. Prove that is divisible by 3 for all .

2. Use the principle of Mathematical Induction to verify that for n, any positive
integer, is divisible by 5.

Suggested Solutions

1. Let denotes the statement that is divisible by 3 for all .

When : , which is divisible by 3 or we can say 9 is a multiple

of 3. is true for (Base Case/Initial Stage)

Assuming that is true for : i.e. .

(Assumption/Hypothesis Stage)

Then for : (Thesis Stage)

Proof

which is true for

Tarakino N.P. (Trockers) ~ 0772978155/ 0717267175

Page 4
 is true for . (Proof Stage)

NB: The proof stage can also be conducted using the method of differences as follows:

is also a multiple of ( This is because that if you subtract consecutive

multiples of a number you also get another multiple of that same number
e.g. )

Since is true for (Conclusion Stage)

HINT

is divisible by 5

is divisible by 4

is divisible by 3

is divisible by

Tarakino N.P. (Trockers) ~ 0772978155/ 0717267175

Page 5
 SUMMATIONS/SERIES

Examples

1. Prove by induction that: for al

2. Prove by induction that:
for all positive integral values of

Suggested Solutions

1. Let denotes the statement that for al

When :

Since is true for (Base Case/Initial Stage)

Assuming that is true for : i.e. (Assumption/Hypothesis

Stage)

Then for : (Thesis Stage)

Proof

Note:
a)
b)

Tarakino N.P. (Trockers) ~ 0772978155/ 0717267175

Page 6
 which is true for

is true for . (Proof Stage)

Since is true for (Conclusion Stage)

2. Let denotes the statement that:

For all positive integral values of ,

When :

Since is true for (Base Case/Initial Stage)

Assuming that is true for : i.e.

(Assumption/Hypothesis Stage)

Then for :
(Thesis Stage)

Proof

Note:
a) The summation of k terms
b) The summation of (k+1) terms

(Bracket Expansion)

Tarakino N.P. (Trockers) ~ 0772978155/ 0717267175

Page 7
 (Factorisation)

which is true for

is true for . (Proof Stage)

Since is true for (Conclusion Stage)

Tarakino N.P. (Trockers) ~ 0772978155/ 0717267175

Page 8
 MATRICES
DIVISIBILITY

Examples

DIVISIBILITY
1. Prove by Mathematical Induction that if then

for all .

Suggested Solution

1. Let denotes the statement that:

If then for all .
When :

Since is true for (Base Case/Initial Stage)

Assuming that is true for : i.e. (Assumption/Hypothesis

Stage)

Then for : (Thesis Stage)

Proof

Note:
a)

Tarakino N.P. (Trockers) ~ 0772978155/ 0717267175

Page 9
 which is true for

is true for . (Proof Stage)

Since is true for (Conclusion Stage)

INTEGRATION
DIVISIBILITY

Example

DIVISIBILITY
1. Use Induction to prove that

Suggested Solution

1. Let denotes the statement that:

When :

Since is true for (Base Case/Initial Stage)

Assuming that is true for : i.e. (Assumption/Hypothesis

Stage)

Tarakino N.P. (Trockers) ~ 0772978155/ 0717267175

Page 10
 Then for :
(Thesis Stage)

Proof

Note:
a) . Then use the method of integration by
parts. Choose to be an expression which varnishes after
performing 1 or more derivations.

Let and

Now use

(Since )

;which is true for

is true for . (Proof Stage)

Since is true for (Conclusion Stage)

Tarakino N.P. (Trockers) ~ 0772978155/ 0717267175

Page 11
 DIFFERENTIATION

DIVISIBILITY
Examples

1. Prove by Induction that .

2. Use Mathematical Induction to prove that if

Suggested Solutions

1. Let denotes the statement that for al

When :

Since is true for (Base Case/Initial Stage)

Assuming that is true for : i.e. (Assumption/Hypothesis Stage)

Then for : (Thesis Stage)

Proof

Note:
a) . Then use the Product Rule.

Tarakino N.P. (Trockers) ~ 0772978155/ 0717267175

Page 12
Let and

Now use .

which is true for

is true for . (Proof Stage)

Since is true for (Conclusion Stage)

2. Let denotes the statement that if for al

When :

Since is true for (Base Case/Initial Stage)

Assuming that is true for : i.e. (Assumption/Hypothesis

Stage)

Then for : (Thesis Stage)

Proof

Note:
b)

(Use the Product Rule)

Tarakino N.P. (Trockers) ~ 0772978155/ 0717267175

Page 13
 which is true for

is true for . (Proof Stage)

Since is true for (Conclusion Stage)

Tarakino N.P. (Trockers) ~ 0772978155/ 0717267175

Page 14
 FACTORIAL NOTATION

Example

Prove by Induction that =(n+1)!-1 for all

Suggested Solution

Let denotes the statement that: = (n+1)!-1 for all

When :

Since is true for (Base Case/Initial Stage)

Assuming that is true for : i.e. =(k+1)!-1 (Assumption/Hypothesis

Stage)

Then for : =[(k+1)+1]!-1

(Thesis Stage)

Proof

Note:
a)
b)

Tarakino N.P. (Trockers) ~ 0772978155/ 0717267175

Page 15
 ; which is true for

is true for . (Proof Stage)

Since is true for (Conclusion Stage)

Tarakino N.P. (Trockers) ~ 0772978155/ 0717267175

Page 16
 COMPOSITE FUNCTIONS AND SEQUENCES
DIVISIBILITY

DIVISIBILITY
Examples

1. If , find:
i)

ii)

iii)
iv) Suggest a formula for
v) Prove your result in (iv) by Mathematical Induction.
2. Given that a sequence is defined by

Prove by induction that

Suggested Solutions

1. i) (Use the Product Rule)

ii)

iii)

iv)
v) The proof has been worked out on the differentiation section.

Tarakino N.P. (Trockers) ~ 0772978155/ 0717267175

Page 17
 2. for al
When :
the given condition
is true for (Base Case/Initial Stage)

Assuming that is true for : i.e. (Assumption/Hypothesis Stage)

Then for : (Thesis Stage)

Proof

(Since )

(Since )

; which is true for

is true for . (Proof Stage)

Since is true for (Conclusion Stage)

Tarakino N.P. (Trockers) ~ 0772978155/ 0717267175

Page 18
 PRACTICE QUESTIONS

The following questions are a compilation of ZIMSEC, Cambridge and

other Examination Boards Past Examinations Questions.

1. Prove by Mathematical Induction that is divisible by for

.

2. Prove that is a multiple of 3 for all positive integers of n.

3. Prove by Mathematical Induction that is a multiple of 5 for all natural

numbers n.

4. Prove that is a multiple of 7, when n is odd.

5. Prove by Mathematical Induction that is divisible by 6 for all natural

numbers n.

6. Prove using the principles of mathematical induction that is divisible by

for all

7. Prove that is a divisible of 5 for all positive integers of n.

8. Prove by induction that: for any .

9. Prove by induction that:

for all

Hence Evaluate

Tarakino N.P. (Trockers) ~ 0772978155/ 0717267175

Page 19
10. Prove by Induction that

for all , where is the set of positive integers.

11. Prove by induction that:

for al

12. Prove by induction that:

for all

13. Use Mathematical Induction to prove that:

for all

14. Use Mathematical Induction to prove that:

for all

15. Prove by induction that for any

16. Prove by induction that for any ;

17. Prove by Induction that

Tarakino N.P. (Trockers) ~ 0772978155/ 0717267175

Page 20
 for all positive integral values of , where and are constants.
18. Prove by induction that:

for all positive integral values of

19. Prove by induction that:

for all

20. a) Prove by induction that for all positive integers n

b) Hence evaluate

21. Prove by Mathematical Induction that if then

for all .

22. Prove by induction that .

23. Prove by Mathematical Induction that if then

for all .

Tarakino N.P. (Trockers) ~ 0772978155/ 0717267175

Page 21
24. Prove by Mathematical Induction that for all .

25. Prove by Mathematical Induction that if then

for all .

26. Prove by Mathematical Induction that if then

for all .

27. Prove by Mathematical Induction that if then

for all .

28. Use Mathematical Induction to prove that if

29. Show that . Hence Prove by Induction that

30. If , then prove by mathematical induction that for :

31. Prove by Induction that .

32. If , show by Induction that

33. It is given that ,

(i) Show that .

(ii) Hence, prove by induction that the statement
,

Tarakino N.P. (Trockers) ~ 0772978155/ 0717267175

Page 22
 is true for all positive integers, , such that

34. Show that . Hence Prove by Induction that

35. Given that where is a constant.

(a) Find expressions for , and , giving your answers in the form

where
(b) Suggest a formula for derivative of in terms of and .
(c) Prove by Induction the suggested derivative of .

36. Prove that for all , .

37. Given that a sequence is defined by

Prove by induction that

38. Given that a sequence is defined by

. Prove by induction that .

39. Use Induction to show that:

for all .

40. Given that , find:

i)
ii)
iii) Suggest a formula for
iv) Prove the result in (iii) by Induction.

Tarakino N.P. (Trockers) ~ 0772978155/ 0717267175

Page 23
ASANTE SANA

Tarakino N.P. (Trockers) ~ 0772978155/ 0717267175

Page 24
*******THERE IS A LIGHT AT THE END OF EVERY TUNNEL *******

CONSTRUCTIVE COMMENTS ON THE FORM

OF THE PRESENTATION, INCLUDING ANY
OMISSIONS OR ERRORS, ARE WELCOME.

***ENJOY***

Nyasha P. Tarakino (Trockers)

+263772978155/+263717267175

ntarakino@gmail.com

Tarakino N.P. (Trockers) ~ 0772978155/ 0717267175

Page 25