Amy glenschool engineering information technology murdoch university

LECTURE 29

Mathematical Induction (Ch. 9)

Then ’n œ N P(n) is true.

Question

Dr Amy Glen (Murdoch University)	MAS162 – Foundations of Discrete Maths	Lecture 29 – S1 2016	3

Chapter 9: Mathematical Induction	4

Principle of Mathematical Induction . . .

I (B) tells us P(0) is true.

I Now (R) with n = 1 tells us P(1) æ P(2) is true, and

P(1) · (P(1) æ P(2)) ∆ P(2)

Frog crossing a pond

Another analogy is to consider a set of identical lily pads, all equally spaced in a line across a pond, with the first and last lily pads adjacent to the two sides of the pond.

What a clever frog!

Chapter 9: Mathematical Induction	6

Analogies

Examples

1

	If we add successive powers of 2, starting with 1 (which is 20), the following pattern emerges:

1 = 1
1 + 2 = 3
1 + 2 + 4 = 7
1 + 2 + 4 + 8 = 15
...

Chapter 9: Mathematical Induction	9

(B) P(i) is true, and

tn = (n ≠ 1)2	for each integer n > 1.

We can prove this using the modified principle of induction . . . 5 Prove that 4 is a factor of 7n≠ 3nfor all integers n > 1. 6 Prove that 2n< (n + 1)! for all integers n > 2.

Values of 2nand n2for the first few natural numbers n appear below.

2n n2

This table shows that “2n> n2” is not true for all numbers n. But it does suggest that “2n> n2” is true for n > 5.