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.

Some overall grading notes based on assignments turned in for those.

• Please make sure your solutions are in the right order when you hand them in - don't make me look through all of your files for each problem.
• Be careful about how you word things with your induction proofs. You prove the base case(s). For the inductive part, you /assume/ the inductive assumption and must /show/ or /demonstrate/ that it works for k+1 or n+1 (you don't /assume/ that it is true for k+1 or n+1).
• The base cases need to be proved, "just" showing an example is not enough.
• You need to have enough explanation for someone to read this, understand it, and be completely convinced. It is not enough to just have a sequence of equations with no explanation.
• For the base cases, you will work out what the base case is, and you need to have a sentence something like - "and this is correct because ...", with the because part depending on the problem. The point is - you don't assume the reader finishes the thought in their mind, you have to finish the thought for them.

And some grading notes particular to each problem.

1. • Giving credit as long as you had a valid tiling and showed how it was built from four 4x4 tilings. I was hoping you would explain it nicely in terms of tracing the induction argument backwards from the 8x8 board, but giving credit even if you did not explain it this way.
   • Note that there should only be one triomino that goes betwen the different 4x4 sections, and it should be the one from the induction argument.
2. • Make sure you visited the lab to demonstrate the proof - that is what this question was asking you to do.
   • Note that as long as you were checked off as okay by the lab I did not look at anything you might have handed in for this problem (some people included the proof in their submission).