### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Class Note for MATH 294A with Professor Savitt at UA

### View Full Document

## 16

## 0

## Popular in Course

## Popular in Department

This 2 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Arizona taught by a professor in Fall. Since its upload, it has received 16 views.

## Popular in Subject

## Reviews for Class Note for MATH 294A with Professor Savitt at UA

### 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: 02/06/15

Some notes on strong induction Matt Ondrus and Ksenija Simic Muller March 7 2007 I found this at httpwww rcfusceduN lototskyPiMuEpinductpdf 771 like to think of weak induction as sort of like climbing a ladder The base case is the bottom rung of the ladder and the induction step shows you how to climb from one rung to the next If you know how to get to the bottom rung and you know how to climb from one rung to the next you can climb to every rung above the bottom one The differencebetween strong and weak induction is in what you need to assume in the induction step For ordinary induction in the ladder metaphor you simply go from the rung you are on up to the next one For strong induction you need to know that all the rungs below the rung you are on are solid in order to step up As a practical matter both have the same logical strength when you apply them since as you climb up the ladder from the bottom rung you sweep through all the intermediate rungs anyway77 There are other useful statements related to induction 0 The wellordering principle it states that every nonempty set of natural numbers has a least element 0 The principle of descent you will see it stated in different forms but in simplest terms it states that if P is a property of natural numbers and if there is a counterexample to P then there is the least counterexample We usually use descent to prove the contrapositive of a statement suppose you want to prove that P holds for all natural numbers assume there is a number n for which it fails by descent you can assume that it is the smallest such if we are able to derive from this that there is a smaller value for which P fails then we get a contradiction so P is in fact always true 0 The principle of in nite descent states that If P is a property of natural numbers and if with the assumption that there exists an n for which Pn is true you could construct a sequence n gt n1 gt n gt H for which P holds then P in fact fails for all n The following are equivalent Weak induction 0 Strong induction Wellordering principle 0 Finite descent 0 In nite descenti By equivalent we mean that they all have the same logical strength ie can prove the same statements though some logicians argue that in nite descent is different from the other four Both descent and in nite descent can often be used when it is not clear how to use weak or strong induction as in the next example Solution of Problem 12 There are no positive integer solutions of I4 y4 22 Use the fact that every positive integer solution of a2 b2 c2 where a b and c are relatively prime can be expressed in terms of two relatively prime numbers m and n where a m2 7 n2 1 2mm and c m2 n2i Notice that we can assume that a b and c are relatively prime since if they are not we can divide the whole expression by their GCF also notice that exactly one of a b is even so assume that this is 12 So suppose you have a solution to I4 y4 22 Applying the above fact to the pythagorean triple I2y2 2 gives 12 p2 7 42 y2 21m and 2 p2 42 Since 2104 is a square and p and 4 have no common factors one of p and 4 must be 2 times a square and the other is an odd square convince yourself this is true And since 117 q themselves form a relatively prime pythagorean triple since 12q2 p2 we can see that there are T and s for which I T2782 4 2T3 and p T232i This means 4 is the one that is 2 times a square 4 2112 and p is an odd square 17 v2 Now 4 2112 2T3 which means T and s are themselves perfect squares because they are relatively primei Yet 7 2 32 p v2 which means v2 is expressible as the sum of fourth powers since T and s are perfect squaresi Yet if we look at the construction of v we see v2 lt 22 which creates our in nite descent since you can repeat the process again a contradiction You can also think of this problem in terms of nite descent if we assume that zy 2 is the smallest triple for which the claim holdsi Logicians would point out here that we were being sloppy because we are creating an in nite descending sequence of triples and not natural numbers as is required but this can easily be remedied by using some form of coding that would assign to each triple a single number and would preserve orderingi Such codings do exist 77Godel numbering

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

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

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