Strong Induction • To prove that P(n) is true for all positive integers n • where P(n) is a propositional function, complete two steps: • Basis Step ○ Verify that the proposition P(1) is true. • Inductive Step ○ Show the conditional statement § [P(1)∧P(2)∧…∧P(k)]→ P(k+1) ○ holds for all positive integers k. • Strong Induction is sometimes called ○ the second principle of mathematical induction ○ complete induction Proof using Strong Induction • Prove that every natural number n 7 can be written as 3p+5q • where p and q are natural numbers • Prove this result using strong induction • Basis Step ○ 8=3×1+5×1 • Inductive Step ○ Inductive hypothesis: The statement is true for any n for k≥n≥8 ○ In particular it is true for k+1−3 (assuming k+1−3≥8) ○ So k+1−3=3p+5q and so k+1=3(p+1)+5q • What happens if k+1=9 or k+1=10? ○ Add those cases into the basis step ○ 9=3×3+5×0 ○ 10=3×0+5×2 Which Form of Induction Should Be Used? • We can always use strong induction instead of mathematical induction. • But there is no reason to use it if it is simpler to use mathematical induction • In fact, the principles of mathematical induction, strong induction, and the well-ordering property are all equivalent. • Sometimes it is clear how to proceed using one of the three methods, but not the other two. Proof of the Fundamental Theorem of Arithmetic • Show that if n is an integer greater than 1 • Then n can be written as the product of primes. • Let P(n) be the proposition that n can be written as a product of primes. • Basis Step ○ P(2) is true since 2 itself is prime. • Inductive Step ○ The inductive hypothesis is P(j) is true for j∈Z with 2≤j≤k ○ To show that P(k+1) must be true under this assumption ○ Two cases need to be considered: ○ If k+1 is prime, then P(k+1) is true. ○ Otherwise, k+1 is composite ○ And it can be written as the product of two positive integers ○ a and b with 2≤a≤b≤k+1 ○ By inductive hypothesis a and b can be written as product of primes ○ Therefore k + 1 can also be written as the product of those primes. • Hence, every integer greater than 1 can be written as product of primes Well-Ordering Property • Well-ordering property ○ Every nonempty set of nonnegative integers has a least element. • The well-ordering property is one of the axioms of the positive integers • The well-ordering property can be used directly in proofs. • The well-ordering property can be generalized. • Definition: A set is well ordered if every subset has a least element. ○ N is well ordered under ≤. ○ The set of finite strings over an alphabet using lexicographic ordering is well ordered. Proof of The Division Algorithm • Use the well-ordering property to prove the division algorithm ○ If a is an integer and d is a positive integer, then ○ there are unique integers q and r with 0≤r d, such that ○ a=dq+4 • Let S be the set of nonnegative integers of the form a=dq, q∈Z. • The set is nonempty since −dq can be made as large as needed • By the well-ordering property, S has a least element r=a−dq_0 • The integer r is nonnegative. • It also must be the case that r d • If it were not, then there would be a smaller nonnegative element in S ○ a−d(q_0+1)=a−dq_0−d=r−d 0 • Therefore, there are integers q and r with 0≤r d
