# DARTMOUTH COSC 030 - 07induction (5 pages)

Previewing pages 1, 2 of 5 page document
View Full Document

## 07induction

Previewing pages 1, 2 of actual document.

View Full Document
View Full Document

## 07induction

50 views

Pages:
5
School:
Dartmouth College
Course:
Cosc 030 - Discrete Math Computer Sci
Unformatted text preview:

Our First Proof by Induction CS 30 Discrete Mathematics Amit Chakrabarti Mathematical Induction Inclusion Exclusion Proof by Induction Template 1 2 3 4 Declare a proof by induction on some integer n 0 DeXine an appropriate predicate P n Write Base case Prove that P 0 is true induction the meat proving P k P k 1 for all k 0 hypothesis a Write Inductive step b Write Assume P k is true for some k 0 c Using math logic show that P k 1 is true Point out where you are using the induction hypothesis 5 Write Thus by mathematical induction it follows that P n is true for all n 0 QED Theorem For all n 0 we have 1 2 n n n 1 2 Proof We use induction on n Let P n be the statement 1 2 n n n 1 2 Base case P 0 says 0 0 0 1 2 which is clearly true Inductive step Assume P k is true for some k 0 by the induction Then 1 2 k k 1 k k 1 2 k 1 hypothesis k 1 k 2 1 k 1 k 2 2 So P k 1 is true We ve proved P k P k 1 for all k 0 By mathematical induction P n is true for all n 0 QED Another Proof by Induction Theorem For all n 1 we have 13 23 n3 n2 n 1 2 4 Proof We use induction on n Let P n be the statement 13 23 n3 n2 n 1 2 4 Base case P 1 says 13 12 1 1 2 4 which is clearly true Inductive step Assume P k is true for some k 1 Then by the 13 23 k3 k 1 3 k2 k 1 2 4 k 1 3 induction k 1 2 k2 4 k 1 hypothesis 2 2 k 1 k 4k 4 4 k 1 2 k 2 2 4 So P k 1 is true Thus by mathematical induction it follows that P n is true for all n 1 QED Size of Power Set Proof by Induction 1 2 Size of Power Set Proof by Induction 2 2 Theorem For every Xinite set S we have P S 2 S Proof We use induction on the size S Let Q n be the statement S S n P S 2n Base case Q 0 says S S 0 P S 1 This is true because S 0 S P S P S 1 Inductive step Assume Q k is true for some k 0 Consider an arbitrary set S with S k 1 Then S is nonempty so we may choose an x S Consider the sets Tinc A P S x A Texc A P S x A DeXine f Tinc Texc by f A A x This f is a bijection so Tinc Texc Tinc Texc and P S Tinc Texc So P S Tinc Texc 2 Texc Also Texc P S x and S x k By the induction hyp Texc 2k Let Q n be the statement S S n P S 2n Base case Q 0 says S S 0 P S 1 This is true because S 0 S P S P S 1 Inductive step Assume Q k is true for some k 0 Consider an arbitrary set S with S k 1 Then S is nonempty so we may choose an x S Consider the sets Tinc A P S x A Texc A P S x A DeXine f Tinc Texc by f A A x This f is a bijection so Tinc Texc Tinc Texc and P S Tinc Texc So P S Tinc Texc 2 Texc Also Texc P S x and S x k By the induction hyp Texc 2k Thus P S 2 Texc 2 2k 2k 1 We have proved that Q k 1 is true Thus by induction it follows that Q n is true for all n 0 QED Strong Induction Proof by Strong Induction Template We have a predicate P on integers n 0 Suppose P 0 is true k 0 P 0 P 1 P 2 P k 1 P k Then n 0 P n is true Why We reason as follows P 0 P 1 so P 1 is true P 0 P 1 P 2 so P 2 is true P 0 P 1 P 2 P 3 so P 3 is true and so on 1 2 3 4 Declare proof by strong induction on some integer n 0 DeXine an appropriate predicate P n Write Base case Prove that P 0 is true the meat P 0 P 1 P k 1 P k for all k 0 a Write Inductive step induction hypothesis b Write Assume P n is true for all n k c Using math logic show that P k is true Point out where you are using the induction hypothesis 5 Write Thus by mathematical induction it follows that P n is true for all n 0 QED Strong Induction Example Theorem Every integer n 2 can be factored into primes i e one or more primes not necessarily all distinct Proof We use induction on n Let P n n can be factored into primes Base case P 2 is trivially true because 2 is prime Inductive step Assume P n is true for all n with 2 n k where k 2 by the Consider P k If k is prime then P k is trivially true induction Otherwise k has a factor x with 1 x k Let y k x hypothesis Since x k P x is true So x can be factored into primes Since x 1 y k x k So P y is true so y can be factored into primes Combining the lists of factors of x and y gives a factorization of k xy into prime factors Thus P k is true Thus by induction it follows that P n is true for all n 2 QED A Mini Matching Quiz Khalil Ellen Weiling Noah Emma Concepts Proof by induction Strong induction Induction hypothesis Theorems Sum of arithmetic series Sum of geometric series class ex Cardinality of power set Prime factorization theorem Study Bee Skills Template for a proof by induction Induction on what The Full Matching Quiz If I guess at random how unlucky do I have to be for such total failure i e score zero Match 2 faces to 2 names probability zero score 1 2 50 Match 5 faces to 5 names probability zero score 44 120 36 7 Match 37 faces to 37 names probability zero score 36 8 Oh dear I scored zero Total failure Counting Derangements Principle of Inclusion Exclusion PIE Notation n 1 2 n Function f n n is called a derangement if i f i i Let Fn number of injective functions f n n Let Dn number of derangements f n n We have seen A1 A2 A1 A2 A1 A2 A1 A2 A3 A1 A2 …

View Full Document

## Access the best Study Guides, Lecture Notes and Practice Exams Unlocking...