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
Questions?
The 2nd Principle of Induction
aka strong induction
Second part of section 4.2
Key part of inductive step in “product of primes” proof:
Proposition: every natual number ≥ 2 is either prime or a product of primes
…if k+1 composite, then k+1 = xy where x ≤ k and y ≤ k and therefore
both are prime or products of primes…
Needn’t start at 1
Progress check 4.10 / Proposition 4.11
For every natural number n ≥ 8, there exist non-negative integers x and y
such that n = 3x + 5y
Basis: n = 8 = 5 × 1 + 3 × 1
And n = 9 = 3×3 + 5×0
And n = 10 = 3×0 + 5×2
Inductive step:
Assume that for each i in 8, 9, …, k for some k ≥ 10 there exist non-negative
integers x and y such that i = 3x + 5y
Prove k+1 = 3a + 5b for some a and b
k+1 = (k-2) + 3
= 3x + 5y + 3 (because 8 ≤ k-2 ≤ k and so = 3x + 5y for some x, y)