Theorem 4.3: (Weak Induction): Let P (n ) be a statement which depends on a natural number n. If

a) (anchor) P (0) is true,

and if

b) (induction) whenever P (k ) is true then so is P (k +1)

then P (n ) is true for all natural numbers n.

Proof: Let n be a natural number. To show that P(n) is true, note that by hypothesis a), the anchoring hypothesis, P(0) is true. The first time we apply the induction hypothesis we conclude that since P(0) is true, then so is P(1). The second time we apply the induction hypothesis, we conclude that since P(1) is true then so is P (2). Continuing. After applying the induction hypothesis n times, we conclude that P(n) is true.