LECTURE 29
Mathematical Induction (Ch. 9)
Then ’n œ N P(n) is true.
Question
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
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!
Analogies
Examples
1 = 1
1 + 2 = 3
1 + 2 + 4 = 7
1 + 2 + 4 + 8 = 15
...
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.
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.

