- Exam 2
- Next Wednesday, Oct. 26
- Material since 1st exam (e.g., proof techniques — direct, contrapositive, contradiction, biconditionals, cases, induction — maybe contextual material such as congruence)
- Rules and format otherwise similar to 1st exam, especially open-references rule
- First part of section 4.2
- Can start with any integer, m, you want
- Prove P(m)
- Prove that P(k) implies P(k+1) when k ≥ m
- Then P(n) holds for all integers n ≥ m
- A Math 239 Extended Principle of Mathematical Induction (not commonly discussed in
textbooks or used, but valid):
- Prove P(m)
- Prove that P(k) implies P(k-1)
- Then P(n) holds for all integers n ≤ m
- Can we include the empty set (n = 0) in our proof that all sets of size n have
2n subsets?
- Extended proposition to “for all integers n ≥ 0…” seems to be true
- {} (n=0) has 1 = 20 subset {}
- New induction proof: basis case is n = 0. Nothing else changes
- Extended proposition to “for all integers n ≥ 0…” seems to be true
- Prove that the sum of powers of 2 from 20 through 2n =
2n+1 - 1
- The 2nd principle of induction
- Last part of section 4.2