Induction Sections 41 and 4 2 of Rosen Fall 2008 CSCE 235 Introduction to Discrete Structures Course web page cse unl edu cse235 Questions cse235 cse unl edu Outline Motivation What is induction Viewed as the Well Ordering Principle Universal Generalization Formal Statement 6 Examples Strong Induction Definition Examples decomposition into product of primes gcd CSCE 235 Fall 2008 Induction 2 Motivation How can we prove the following proposition x S P x For a finite set S s1 s2 sn we can prove that P x holds for each element because of the equivalence P s1 P s2 P sn For an infinite set we can try to use universal generalization Another more sophisticated way is to use induction CSCE 235 Fall 2008 Induction 3 What Is Induction If a statement P n0 is true for some nonnegative integer say n0 1 Suppose that we are able to prove that if P k is true for k n0 then P k 1 is also true P k P k 1 It follows from these two statement that P n is true for all n n0 that is n n0 P n The above is the basis of induction a widely used proof technique and a very powerful one CSCE 235 Fall 2008 Induction 4 The Well Ordering Principle Why induction is a legitimate proof technique At its heart induction is the Well Ordering Principle Theorem Principle of Well Ordering Every nonempty set of nonnegative integers has a least element Since every such has a least element we can form a base case using the least element as the base case n0 We have then proceed to establish that the set of integers n n0 such that P n is false is actually empty Thus induction both weak and strong forms are logical equivalences of the well ordering principle CSCE 235 Fall 2008 Induction 5 Another View To look at it in another way assume that the statements 1 P no 2 P k P k 1 are true We can now use a form of universal generalization as follows Say we choose an element c of the UoD We wish to establish that P c is true If c n0 then we are done Otherwise we apply 2 above to get P n0 P n0 1 P n0 1 P n0 2 P n0 1 P n0 3 P c 1 P c Via a finite number of steps c n0 we get that P c is true Because c is arbitrary the universal generalization is established and n n0 P n CSCE 235 Fall 2008 Induction 6 Outline Motivation What is induction Viewed as the Well Ordering Principle Universal Generalization Formal Statement 6 Examples Strong Induction Definition Examples decomposition into product of primes gcd CSCE 235 Fall 2008 Induction 7 Induction Formal Definition 1 Theorem Principle of Mathematical Induction Given a statement P concerning the integer n suppose 1 P is true for some particular integer n0 P n0 1 2 If P is true for some particular integer k n0 then it is true for k 1 Then P is true for all integers n n0 that is n n0 P n is true CSCE 235 Fall 2008 Induction 8 Induction Formal Definition 2 Showing that P n0 holds for some initial integer n0 is called the Basis Step The assumption P k is called the induction hypothesis Showing the implication P k P k 1 for every k n0 is called the Induction Step Together induction can be expressed as an inference rule P n0 k n0 P k P k 1 n n0 P n CSCE 235 Fall 2008 Induction 9 Steps 1 2 3 4 Form the general statement Form and verify the base case basis step Form the inductive hypothesis Prove the induction step CSCE 235 Fall 2008 Induction 10 Example A 1 Prove that n2 2n for all n 5 using induction We formalize the statement P n n2 2n Our base case is for n 5 We directly verify that 25 52 25 32 so P 5 is true and thus the basic step holds We need now to perform the induction step CSCE 235 Fall 2008 Induction 11 Example A 2 We assume P k holds the inductive hypothesis Thus k2 2k Multiplying by 2 we get 2k2 2k 1 By a separate proof we show that for all k 5 k 1 2 k2 2k 1 k2 5k k2 k2 2k2 Using transitivity we get that k 1 2 2k2 2k 1 Thus P k 1 holds CSCE 235 Fall 2008 Induction 12 Example B 1 Prove that for any n 1 i 1n i2 n n 1 2n 1 6 The base case is easily verified 12 1 1 1 1 2 1 6 We assume that P k holds for some k 1 so i 1k i2 k k 1 2k 1 6 We want to show that P k 1 holds that is i 1k 1 i2 k 1 k 2 2k 3 6 We rewrite this sum as i 1k 1 i2 12 22 k2 k 1 2 i 1k i2 k 1 2 CSCE 235 Fall 2008 Induction 13 Example B 2 We replace i 1k i2 by its value from the inductive hypothesis i 1k 1 i2 i 1k i2 k 1 2 k k 1 2k 1 6 k 1 2 k k 1 2k 1 6 6 k 1 2 6 k 1 k 2k 1 6 k 1 6 k 1 2k2 7k 6 6 k 1 k 2 2k 3 6 Thus we established that P k P k 1 Thus by the principle of mathematical induction we have n 1 i 1n i2 n n 1 2n 1 6 CSCE 235 Fall 2008 Induction 14 Example C 1 Prove that for any integer n 1 22n 1 is divisible by 3 Define P n to be the statement 3 22n 1 We note that for the base case n 1 we do have P 1 22 1 1 3 is divisible by 3 Next we assume that P k holds That is there exists some integer u such that 22k 1 3u We must prove that P k 1 holds That is 22 k 1 1 is divisible by 3 CSCE 235 Fall 2008 Induction 15 Example C 2 Note that 22 k 1 1 2222k 1 4 22k 1 The inductive hypothesis 22k 1 3u 22k 3u 1 Thus 22 k 1 1 4 22k 1 4 3u 1 1 12u 4 1 12u 3 3 u 1 a multiple of 3 We conclude by the principle of mathematical induction for any integer n 1 22n 1 is divisible by 3 CSCE 235 Fall 2008 Induction 16 Example D Prove that n 2n for all n 4 The base case holds for n 4 because 4 24 24 16 We assume that k 2k for some integer k 4 which is our inductive hypothesis We must prove the P k 1 holds k 1 k k 1 2k k 1 Because k 4 k 1 5 2 …
View Full Document
Unlocking...