Monday April 14
More about induction proofs.
v1. Case check: either there are no counterexamples (yay), or there is a least one; ... we find a smaller one, and reach a contradiction.
v2. A rewriting of that.
v3. [the contrapositive] if P(m) is true for all m < n, then ... it's true for n; "hence we're done".
Example: every natural number is a product of prime numbers.
Weak induction only uses n-1 to prove n, rather than all m < n to prove n.
Examples: every natural number is even or odd. The sum of the first n integers is n(n+1)/2.
v1. Case check: either there are no counterexamples (yay), or there is a least one; ... we find a smaller one, and reach a contradiction.
v2. A rewriting of that.
v3. [the contrapositive] if P(m) is true for all m < n, then ... it's true for n; "hence we're done".
Example: every natural number is a product of prime numbers.
Weak induction only uses n-1 to prove n, rather than all m < n to prove n.
Examples: every natural number is even or odd. The sum of the first n integers is n(n+1)/2.
posted by Allen Knutson @ 12:38 PM
0 Comments:
Post a Comment
<< Home