Honors Discrete Mathematics
Honors Discrete Mathematics MAD 2104
Popular in Course
Popular in Mathematics Discrete
This 8 page Class Notes was uploaded by Dino Corwin on Monday October 12, 2015. The Class Notes belongs to MAD 2104 at Florida Atlantic University taught by Jorge Viola-Prioli in Fall. Since its upload, it has received 22 views. For similar materials see /class/221637/mad-2104-florida-atlantic-university in Mathematics Discrete at Florida Atlantic University.
Reviews for Honors Discrete Mathematics
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/12/15
20SMALLEST COUNTEREXAMPLE Sections 20 and 21 are both governed by a fundamental principle valid on the set of natural numbers WEquot Ordered Principle Every non empty set of natural numbers has a least element This is an axiom hence not to be proved but accepted whose validity we do not hesitate to accept Notice that if we allow negative integers the principle fails to hold Spotting that least element may or may not be easy J Viola Prioli EXAMPLE 1 Let X n E N 6n and 38 lt n This X is nonempty since 60 is in X Clearly the least element is 42 EXAMPLE 2 Let X n E N n is prime of the form 13t 1 This X is non empty since 53 E X In fact the least element is 53 EXAMPLE 3 Let X n E N n is prime and n gt 10703 Although by Euclid s theorem we know there are primes as large as we want and so this set X is non empty it is not obvious what the rst element ofX is although we know it exists by the Well Ordered Principle The method of Smallest Counterexample and its cousin the method of Induction are used to prove the validity of a statement that involves all the natural numbers In other words to prove a list of in nitely many statements one for each n These statements usually carry the expressions quotprove that for all n or V n although sometimes is hidden like in for any given nite set Observe that in this case we can rephrase it as for any set of n elements J Viola Prioli EXAMPLES a 1 144lt 3 is not a list of statements It is just one easily veri ed since 1 o254 2441 lt 3 b 7 divides 7C3 is not a list of statements It is true since 7C3 35 7 x 5 c 1 1nn lt 3 V natural n 2 1 is a list of statements It claims that the inequality holds anytime we substitute n for an integer value greater than 0 NOTE Compare c with a before proceeding d 2n 3n s 5n V natural n 2 1 is a list of statements We will prove later that this statement is true J Viola Prioli A proof by Smallest Counterexample is a proof by contradiction It works this way in four steps 1 Assume for the sake of a contradiction that the statement is false Since the negation of V is El we are saying that there exists ONE false statement down our list By the Well Ordered Principle we choose the least of the false statements But what do we mean by the least Just the very rst FALSE statement we have down the list Call it the kth statement Thus for n k the statement is FALSE 2 Verify that k is NOT 1 3 We now have that the statements are true for n 1 2 k l but it is false for k 4 Try to arrive to a contradiction J Viola Prioli If you succeed you have proved that no such counterexample exists and so the whole statement is true for every n Observe the difference between verifying the statement is true for SOME values of n and the method we just presented ILLUSTRATION Prove that 2n 3 s 5n V natural n 2 1 Proof We can easily verify that the statement is true for n 1 since it will read 2 3 s 5 for n 2 since it will read 4 9 s 25 and so on But that is NOT a proof of the statement for all n J Viola Prioli Step 1 Assume thus there exists a counterexample and pick n k the smallest counterexample Step 2 Since we showed above that for n 1 is true we have that k gt 1 Step 3 We now have that the statement is true for n 1 2 k 1 but it is false for k Unravel this 2n 3 s 5n V natural n 1 2 k 1 is true but 2k 3k s 5k is false Step 4 try to arrive to a contradiction This is always the hard part In our case by we have 239 3 s 539 Multiply both sides by 5 to get 5 2 5 3 s 5 5 5quot Now observe that 2k 3k 2 2 3 3 lt 5 2 5 3 s 5 5 5quot We have arrived to 2k 3k s 5quot which shows that the statement is true for n k But this is a contradiction because it was false for n k We are done J Viola Prioli The following application is in the textbook The Fibonacci sequence is recursively de ned by setting F0 1 F1 1 and Fn Fn1 Fn2 for all n 2 2 The rst terms are therefore 1 1 2 3 5 8 13 21 34 THEOREM Fn s 17n for all n 2 0 Proof Since for n 1 2 the inequality holds we have that the statement is true for n 1 and n 2 Assume there is a counterexample and pick k the smallest counterexample We just observed that k gt 2 Hence Fn s 17n for all n up to k 1 but the inequality is false for n k J Viola Prioli We will try to arrive to a contradiction Both for k 2 and k l the statement is true therefore we have Fk2 s 17quot 2 and Fk1 s 17 Next we add both inequalities Fk2 FMS 17k392 17 The left hand side is Fk so Fk s 17k2 17k1 17k2 17 1 17k227 lt 17k2289 17k2 172 17k So we obtained that Fk s 17k showing that the statement is true for n k This is a contradiction because it was assumed false for n k We are done A remarkable discussion problem A ball is placed in a corner of a pool table of dimensions m and n both are integers It is then hit at a 45degree angle and it starts bouncing on the edges Prove that it will hit a corner J Viola Prioli