Induction

Assignment

Some problems are from Mathematics for Computer Science.

1. See the proof related to tiling from the Induction (II) page in the OneNote notes (in the Proofs section). Consider an 8x8 board with the "red" or missing square being the one in the lower right corner. Show how the proof by induction would construct a valid tiling for this board.
2. Consider the formula for a geometric sum. This is given in MCS problem 5.4 and also here on Wikipedia. Study the proof of the formula using induction and practice giving this proof to yourself (on the board, on paper, or in a document). Visit the CS help lab and give a demo of the proof to one of the lab assistants. You will have at most 10 minutes to complete the argument, and if you cannot get it by then you will need to come back and try again another time. If you are able to give the proof properly, the lab assistant will let you know that you have completed it and they will sign off on it in this document.
3. MCS problem 5.2 - finding the problem in an incorrect induction proof for a tiling problem.
4. MCS problem 5.7 - finding the problem in an incorrect induction proof for an arithmetic sum.
5. MCS problem 5.12 - prove the distributive law of intersection over union.
6. MCS problem 5.13 - prove a formula about the area of the Koch snowflake fractal.
7. MCS problem 5.17 - prove a formula about the number of satisfying assignments for a certain logical formula construction.
8. MCS problem 5.23 - determine what is true given certain assumptions.
9. MCS problem 5.28 - determine what is true and prove it using induction, see also problem 5.32.
10. MCS problem 5.31 - a strong induction proof that is a little tricky.