Page 25 - Chapter 2

 Strong Induction

Weak Induction Strong Induction

Basis Step P(n o) is true P(n o) is true

(or the first several (or the first several

statements are true) statements are true)

Induction P(k)  P(k+1) P(n0) ∧P(n1) ∧… P(k)

Step is a tautology  P(k+1)

is a tautology

• Example 7:

Prove that every positive integer n>1 can be written

a1
a2
as
uniquely as p p …p , where p i are primes and p 1<p 2<..P s
2
s
1
1
Basis Step : P(2) is true, since 2 is prime and 2 = 2 (unique )
Induction Step: Assuming P(2), P(3), … P(k) are true
1
if k+1 is prime, then k+1= (k+1)

if k+1 is not prime, then we let k+1=Lm, where L, m are

positive integers less than k+1. Using P(L) and P(m) are true,

bs
b2
we have k+1=Lm= q 1 b1 q …q (unique form)
2
s
Why? Proof by contradiction