6.042/18.] Mathematics for Computer Science February 11, 2005 Srini devadas and Eric Lehman Notes for recitation 4 1 Strong Induction Recall the principle of strong induction Principle of Strong Induction. Let P(n)be a predicate. If ·P(0) is true,an for all n∈NP(O)∧P(1).…AP(m) implies F(n+1), then P(n) is true for all nE N As an example, lets derive the fundamental theorem of arithmetic Theorem 1. Every positive integer n >2 can be written as the product of primes Proof. The proof is by strong induction. Let P(n) be the statement that n can be written as the product of primes Base case: 2 is itself a prime, so P(2)hold Inductive case: We show that P(2)A P(3).P(n)= P(n +1)is true. Assume that P(2), P(3),.P(n)are true. Consider n +1. If n+ l is a prime number, P(n +1)holds Otherwise, n+ 1 is a composite number; thus it has factors 2 <u,v<n+ l such that uU=n+l. By the inductive hypothesis, u= lli P: for primes Pi and v=li P; for primes pi, so therefore, n+1=lip:lpi, i.e. P(n+1)is true. By the principle of strong induction, P(n)is true for all n>2� � � � 6.042/18.062J Mathematics for Computer Science February 11, 2005 Srini Devadas and Eric Lehman Notes for Recitation 4 1 Strong Induction Recall the principle of strong induction: Principle of Strong Induction. Let P(n) be a predicate. If • P(0) is true, and • for all n ∈ N, P(0) ∧ P(1). . . ∧ P(n) implies P(n + 1), then P(n) is true for all n ∈ N. As an example, let’s derive the fundamental theorem of arithmetic. Theorem 1. Every positive integer n ≥ 2 can be written as the product of primes. Proof. The proof is by strong induction. Let P(n) be the statement that n can be written as the product of primes. Base case: 2 is itself a prime, so P(2) holds. Inductive case: We show that P(2) ∧ P(3). . . P(n) ⇒ P(n + 1) is true. Assume that P(2), P(3), . . . P(n) are true. Consider n + 1. If n + 1 is a prime number, P(n + 1) holds. Otherwise, n + 1 is a composite number; thus it has factors 2 ≤ u, v < n + 1 such that u v = n + 1. By the inductive hypothesis, u = i pi for primes pi and v = j · pj for primes pj , so therefore, n + 1 = i pi pj · , i.e. P(n + 1) is true. By the principle of strong induction, P(n) is true for all n ≥ 2