Page 23 - Chapter 2

 To Prove ∀n>n P(n)

0
where n is some fixed integer

0

Two Steps:

1) Basis Step

Prove that P(n ) is true
0
2) Induction Step

Prove that P(k) => P(k+1) is a tautology

(if P(k) is true, then P(k+1) must be true)

• EXAMPLE 1 :

Prove that for all n>0

1+2+3…+n = n(n+1)/2

Solution: let P(n)=n(n+1)/2

Basis step: P(1) = 1 = 1*2/2=1 is true.

Induction Step: assuming P(k) is true, then

P(k+1) = 1+2 + 3 … + k +(k+1)

= P(k) +(k+1)

= k (k+1)/2 +(k+1) P(k) is true

= (k+1)(k+2)/2

= P(k+1)