# DARTMOUTH COSC 030 - 07induction (5 pages)

Previewing pages*1, 2*of 5 page document

**View the full content.**## 07induction

Previewing pages
*1, 2*
of
actual document.

**View the full content.**View Full Document

## 07induction

0 0 45 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

View Full Document