### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Note 2 for MATH 300 at UMass

### View Full Document

## 15

## 0

## Popular in Course

## Popular in Department

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

## Similar to Course at UMass

## Popular in Subject

## Reviews for Note 2 for MATH 300 at UMass

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

Math 300 Fall 2008 Note 2 Zhigang Han7 Umass at Amherst 1 Mathematical Induction 11 Mathematical Induction o Principle of Mathematical Induction Let Pn be a statement depending on n E N If 1 P1 is TRUE 2 Vk 211 Pk 1 then Pn is TRUE for all n E N Rmk Step 1 is the base case check Step 2 is the induction step To prove step 27 we assume Pk is TRUE induction hypothesis7 and use this to prove Pk 1 is TRUE Rmk The Principle of Mathematical Induction is an immediate con sequence of the wellordering principle which states that any nonempty subset of N always contains a smallest element Try to prove yourself that the well ordering principle implies the principle of mathematical induction Eg 1 Provethat12nforalln ll Eg 2 Provethat 1222n2 H2foralln ll V L Rmk One can use sigma notation to rewrite Eg 2 as Z i2 i0 Rmk In all the examples above7 we need to know the answer before using the mathematical induction to prove it What ifwe are not given the answer nn 12n 1 6 V L V L Eg 3 Find the sum and 22 directly i0 i0 V L Eg 4 Find the sum 23 then use mathematical induction to prove it i0 Eg 5 Prove that z 7 y contains the factor x 7 y for all n E N Eg 6 What s the maximum number of regions can 71 lines divide a plane into Prove your result Eg 7 Tower of Hanoi puzzle The Tower of Hanoi puzzle was invented by the French mathematician Edouard Lucas in 1883 We are given a tower of n disks initially stacked in increasing size on one of three pegs The objective is to transfer the entire tower to one of the other pegs moving only one disk at a time and never a larger one onto a smaller Prove that one can solve the puzzle by 2 7 1 moves Eg 8 The following argument is intended to prove by mathematical induc tion that all horses are of the same color Find the error Proof If there is only one horse there is only one color ii Assume that for any set of k horses there is only one color Now look at any set of k 1 horses We order them as 1 2 3 k k 1 Consider the sets 123 k and 234 k 1 Each is a set of only k horses therefore within each there is only one color But the two sets overlap so there must be only one color among all k 1 horses This proves that all horses are of the same color Variations of mathematical induction 0 The base case does not have to be P1 For instance to prove V71 2 2 Pn the base case should be P2 0 Multiple base cases lfP1 and P2 are both TRUE and for all k 2 1 Pk A Pk 1 Pk 2 then Pm is TRUE for all n e N 0 Strong Mathematical Induction lf P1 is TRUE and for all k 2 1 P1 AP2 A APk Pk 1 then Pm is TRUE for all n e N Rmk The well ordering principle implies the strong mathematical in duction Prove it ii Clearly7 the strong mathematical lnduction implies the mathematical induction Can you prove it In fact7 one can show these two forms of mathematical induction are equivalent Eg 9 Use Strong Mathematical lnduction to prove that every integer greater than or equal to 2 has a prime factor 12 Recursion Def 1 A recursion is a method of de ning functions in which the function calls itself The recursion continues until it reaches the base or stopping case Rmk There may be one or more stopping cases Eg 1 and 2 below have one stopping case7 while Eg 3 has two stopping cases Eg 1 fn fn71 71 ifn 2 2 and f1 1 Eg 2 anan1mn1 15ifn22anda1 Eg 3 Fibonacci Series Fn n11Fn12 if n 2 3 and F2 1F1 1 Eg 4 Prove that in Eg17 n yLZ Hl for all n 1 Eg 5 Prove that in Eg 201 L for all n 1 Eg 6 Prove that in Eg 37 Fn 7 for all n 1 Eg 7 Use mathematical induction to prove the following formulas i fn fn71 2fn72 if 71 Z 3 and f2 57101 2 Answers fn 2 17 71 ii an QanA 7 Qan2 if n 2 3 and a1 2 a2 0 Answers an 1 1 7 iii gn 4gn1 7 4gn2 if n 2 3 and 91 67 92 20 Answers gn 2n 1 2

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

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

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

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