Notes Induction Slides by Christopher M Bourke Instructor Berthe Y Choueiry Spring 2006 Computer Science Engineering 235 Introduction to Discrete Mathematics Section 3 3 of Rosen cse235 cse unl edu Introduction Notes How can we prove the following quantified statement s SP x I 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 I We can use universal generalization for infinite sets I Another more sophisticated way is to use Induction What is Induction Notes I If a statement P n0 is true for some nonnegative integer say n0 1 I 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 I 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 The Well Ordering Principle I Notes Why is induction a legitimate proof technique At its heart is the Well Ordering Principle 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 Another View I Notes To look at it another way assume that the statements P n0 1 P k P k 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 Another View II Notes Otherwise we apply 2 above to get P n0 P n0 1 P n0 2 P n0 3 P c 1 P c 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 Induction I Notes Formal Definition 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 Induction II Notes Formal Definition I 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 I Showing the implication P k P k 1 for every k n0 is called the Induction Step I Together induction can be expressed as an inference rule P n0 k n0 P k P k 1 n n0 P n Example I Notes 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 Example I Notes Continued We now perform the induction step and assume that P k is true Thus k 2 2k Multiplying by 2 we get 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 Using transitivity we get that k 1 2 2k 2 2k 1 Example II Notes Example Prove that for any n 1 n X i2 i 1 n n 1 2n 1 6 The base case is easily verified 1 1 2 1 1 12 1 6 Now assume that P k holds for some k 1 so k X i 1 i2 k k 1 2k 1 6 Example II Notes Continued We want to show that P k 1 is true that is we want to show that k 1 X k 1 k 2 2k 3 i2 6 i 1 However observe that this sum can be written k 1 X i 1 i2 12 22 k 2 k 1 2 k X i 1 i2 k 1 2 Example II Notes Continued k 1 X i2 i 1 k k 1 2k 1 k 1 2 6 k k 1 2k 1 6 k 1 2 6 6 k 1 k 2k 1 6 k 1 6 k 1 2k 2 7k 6 6 k 1 k 2 2k 3 6 Example II Notes Continued Thus we have that k 1 X i 1 k 1 k 2 2k 3 6 so we ve established that P k P k 1 Thus by the principle of mathematical induction n X i 1 i2 n n 1 2n 1 6 Example III Notes Example Prove that for any integer n 1 22n 1 is divisible by 3 Define P n to be the statement that 3 22n 1 Again we note that the base case is n 1 so we have that 22 1 1 3 which is certainly divisible by 3 We next assume that P k holds That is we assume that there exists an integer such that 22k 1 3 Example III Notes Continued Note that 22 k 1 1 4 22k 1 By the induction hypothesis 22k 3 1 applying this we get that 22 k 1 1 4 3 1 1 12 4 1 12 3 3 4 1 And we are done since 3 divides the RHS it must divide the LHS Thus by the principle of mathematical induction 22n 1 is divisible by 3 for all n 1 Example IV Notes Example Prove that n 2n for all n 4 The base case holds since 24 4 24 16 We now make our inductive hypothesis and assume that k 2k for some integer k 4 Since k 4 it certainly is the case that k 1 2 Therefore we have that k 1 k 1 k 2 2k 2k 1 So by the principle of mathematical induction we have our desired result Example V Notes Example Let m Z and suppose that x y mod m Then for all n 1 xn y n mod m The base case here is trivial as it is encompassed by the assumption Now assume that it is true for some k 1 xk y k mod m Example V Notes Continued Since multiplication of corresponding sides of a congruence is still a congruence we have x xk y y k mod m xk 1 y k 1 mod m And so Example VI Notes Example Show that n X i3 i 1 n X 2 i i 1 for all n 1 The base case is trivial since 13 1 2 The induction hypothesis will assume that it holds for some k …
View Full Document
Unlocking...