Induction CSE235 Induction Introduction Preliminaries Formal Statement Examples Slides by Christopher M Bourke Instructor Berthe Y Choueiry Strong Induction More Examples Spring 2006 Computer Science Engineering 235 Introduction to Discrete Mathematics 1 85 Section 3 3 of Rosen Introduction Induction CSE235 How can we prove the following quantified statement Introduction Preliminaries Formal Statement Examples Strong Induction More Examples 2 85 s SP x Introduction Induction CSE235 How can we prove the following quantified statement Introduction Preliminaries s SP x Formal Statement Examples Strong Induction More Examples 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 3 85 Introduction Induction CSE235 How can we prove the following quantified statement Introduction Preliminaries s SP x Formal Statement Examples Strong Induction More Examples 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 We can use universal generalization for infinite sets 4 85 Introduction Induction CSE235 How can we prove the following quantified statement Introduction Preliminaries s SP x Formal Statement Examples Strong Induction More Examples 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 We can use universal generalization for infinite sets Another more sophisticated way is to use Induction 5 85 What is Induction Induction CSE235 Introduction Preliminaries Formal Statement Examples Strong Induction More Examples 6 85 If a statement P n0 is true for some nonnegative integer say n0 1 What is Induction Induction CSE235 Introduction Preliminaries Formal Statement Examples Strong Induction More Examples 7 85 If a statement P n0 is true for some nonnegative integer say n0 1 Also 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 What is Induction Induction CSE235 Introduction Preliminaries Formal Statement Examples Strong Induction More Examples 8 85 If a statement P n0 is true for some nonnegative integer say n0 1 Also 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 statements that P n is true for all n n0 I e n n0 P n What is Induction Induction CSE235 Introduction Preliminaries Formal Statement Examples Strong Induction More Examples If a statement P n0 is true for some nonnegative integer say n0 1 Also 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 statements that P n is true for all n n0 I e n n0 P n This is the basis of the most widely used proof technique Induction 9 85 The Well Ordering Principle I Induction CSE235 Introduction Why is induction a legitimate proof technique At its heart is the Well Ordering Principle Preliminaries Formal Statement Examples Strong Induction More Examples Theorem Principle of Well Ordering Every nonempty set of nonnegative integers has a least element Since every such set has a least element we can form a base case We can 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 10 85 Another View I Induction CSE235 Introduction To look at it another way assume that the statements Preliminaries Formal Statement Examples Strong Induction More Examples P n0 P k P k 1 1 2 are true We can now use a form of universal generalization as follows Say we choose an element from the universe of discourse c We wish to establish that P c is true If c n0 then we are done 11 85 Another View II Induction Otherwise we apply 2 above to get CSE235 Introduction Preliminaries Formal Statement Examples Strong Induction P n0 P n0 1 P n0 2 P n0 3 P c 1 P c More Examples Via a finite number of steps c n0 we get that P c is true Since c was arbitrary the universal generalization is established n n0 P n 12 85 Induction I Formal Definition Induction CSE235 Introduction Theorem Principle of Mathematical Induction Preliminaries Given a statement P concerning the integer n suppose Formal Statement 1 P is true for some particular integer n0 P n0 1 Examples 2 If P is true for some particular integer k n0 then it is true for k 1 Strong Induction More Examples Then P is true for all integers n n0 i e n n0 P n is true 13 85 Induction II Formal Definition Induction CSE235 Introduction Preliminaries Formal Statement Examples Strong Induction More Examples Showing that P n0 holds for some initial integer n0 is called the Basis Step The statement P n0 itself is called the inductive 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 14 85 Example I Induction CSE235 Introduction Preliminaries Formal Statement Examples Strong Induction More Examples 15 85 Example Prove that n2 2n for all n 5 using induction Example I Induction CSE235 Introduction Preliminaries Formal Statement Examples Strong Induction More Examples 16 85 Example Prove that n2 2n for all n 5 using induction We formalize the statement as P n n2 2n Example I Induction CSE235 Introduction Preliminaries Formal Statement Examples Strong Induction More Examples Example Prove that n2 2n for all n 5 using induction We formalize the statement as P n n2 2n Our base case here is for n 5 We directly verify that 25 52 25 32 and so P 5 is true and thus the induction hypothesis holds 17 85 Example I Continued Induction CSE235 Introduction Preliminaries Formal Statement Examples Strong Induction More Examples 18 85 We now perform the induction step and assume that P k is true Thus k 2 2k Example I Continued Induction CSE235 Introduction We now perform the induction step and assume that P k is true Thus k 2 2k Preliminaries Formal Statement Multiplying by 2 we get Examples Strong Induction More Examples 19 85 2k 2 2k 1 Example I Continued Induction CSE235 Introduction We now perform the induction step and assume that P k is true Thus k 2 2k Preliminaries Formal Statement Multiplying by 2 we get Examples Strong Induction More Examples 2k 2 2k 1 By a separate proof we can show that for all k 5 2k 2 k 2 5k k 2 2k 1 k 1 2 20 85 Example I Continued Induction CSE235 Introduction We now perform the induction step and
View Full Document
Unlocking...