DARTMOUTH COSC 030 - 07induction (5 pages)

Previewing pages 1, 2 of 5 page document View the full content.
View Full Document

07induction



Previewing pages 1, 2 of actual document.

View the full content.
View Full Document
View Full Document

07induction

45 views


Pages:
5
School:
Dartmouth College
Course:
Cosc 030 - Discrete Math Computer Sci
Discrete Math Computer Sci Documents

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



View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view 07induction and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view 07induction and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?