CSC236H5 Lecture Notes - Lecture 2: Natural Number, Empty String, Structural Induction
16 Sep 2017
School
Department
Course
Professor
Document Summary
We want to prove that every natural number greater than 1 can be written as a product of primes. 2 = 2 (2 itself is prime) 28 = 2 * 2 * 7. 100 = 5 * 5 * 2 * 2. 101 = 101 (101 itself is prime) Prove that every natural number greater than 1 can be written as a product of primes. In a proof by simple induction: the base case cannot be proved, the inductive hypothesis (i. h. ) can"t be stated c: the proof is not possible. It is difficult to use the i. h. to prove the inductive case. Suppose we know that 101 can be written as a product of primes. 2, 17 and 3 are prime numbers, therefore it is a product of primes. With simple induction, we can only look at 101 or 102. you will need to use complete induction. P + 1 n b (n.
