Download as:
Rating : ⭐⭐⭐⭐⭐
Price: $10.99
Language:EN
Pages: 10

Amy glenschool engineering information technology murdoch university

LECTURE 29

Mathematical Induction (Ch. 9)

Dr Amy Glen (Murdoch University)
Lecture 29 – S1 2016
1
3

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)

MAS162 – Foundations of Discrete Maths
4

I For the recursive step (R), we need only prove that P(n) æ P(n + 1) is true for some n.

Then it works for every n, so that we have really proved that

MAS162 – Foundations of Discrete Maths
5

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

MAS162 – Foundations of Discrete Maths
6

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.

MAS162 – Foundations of Discrete Maths
11

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

n
0 1 2 3 4 5 6 7 8
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.

Copyright © 2009-2023 UrgentHomework.com, All right reserved.