### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Honors Discrete Mathematics MAD 2104

FAU

GPA 3.8

### View Full Document

## 22

## 0

## 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

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

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

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.