1Appendix A
Basic Proof
Techniques
Induction
2Appendix A
Basic Proof
Techniques
Correctness proofs
We prove the
correctness
of iterative algorithms
with the help of induction.
3Appendix A
Basic Proof
Techniques
Weak induction
Lemma: The sum of all integers from 1 to n is equal to n(n+1)/2.
4Appendix A
Basic Proof
Techniques
Weak induction
Lemma: The sum of all integers from 1 to n is equal to n(n+1)/2.
Proof:
5Appendix A
Basic Proof
Techniques
Strong induction
Lemma: Every amount of postage of 12 cents or more can be formed using just
4-cent and 5-cent stamps.
6Appendix A
Basic Proof
Techniques
Strong induction
Lemma: Every amount of postage of 12 cents or more can be formed using just
4-cent and 5-cent stamps.
Proof:
7Appendix A
Basic Proof
Techniques
Pigeonhole principle
8Appendix A
Basic Proof
Techniques
Correctness proofs
Another useful principle:
Pigeonhole principle
(box principle)
9Appendix A
Basic Proof
Techniques
Pigeonhole principle
Suppose there were 10 pigeons and 9 pigeonholes.
If all the pigeons flew into one of the pigeonholes,
what could you guarantee to be true?
a) All of the pigeonholes would be filled.
b) There is at least one pigeonhole with exactly 2 pigeons.
c) There is at least one pigeonhole with exactly 1 pigeon.
d) There is at least one pigeonhole with at least 2 pigeons.
e) All of the above.
10Appendix A
Basic Proof
Techniques
Pigeonhole principle
Suppose there were 10 pigeons and 9 pigeonholes.
If all the pigeons flew into one of the pigeonholes,
what could you guarantee to be true?
a) All of the pigeonholes would be filled.
b) There is at least one pigeonhole with exactly 2 pigeons.
c) There is at least one pigeonhole with exactly 1 pigeon.
d) There is at least one pigeonhole with at least 2 pigeons.
e) All of the above.
There are h pigeonholes and p=p1+p2+…+ph pigeons,
where pi is the number of pigeons in pigeonhole i=1, 2, …, h.
If p>h, then there exists at least one i out of {1, 2, …, h} with pi > 2.
Contrapositive: If for all i out of {1, 2, …, h} pi < 2 then p
What they probably meant is: If there are h pigeonholes and p>9h pigeons, then there are in at least one hole >= 10 pigeons.
(on the slides we have: If there are h pigeonholes and p>h pigeons, the there are in at least one hole >= 2 pigeons.)
Foliennummer 1
Correctness proofs
Weak induction
Weak induction
Strong induction
Strong induction
Foliennummer 7
Correctness proofs
Pigeonhole principle
Pigeonhole principle
Points in a square
Points in a square
Practicing the use of the pigeonhole principle