Examples of weak induction proofs.
Thm: 1 + 2 + ... + n = (n+1 choose 2).
Thm: The number of subsets of X is 2|X|, for X finite.
Thm: If G is a finite graph, the sum of the degrees is even.
Next time: Euclid's algorithm for computing GCDs, and a proof that it works, using strong induction.
No comments:
Post a Comment