Lecture 9

We looked at the outline for an induction proof and did three example proofs

• sum of i*2^i (for i from 2 up to n) equals (n-1)2^{n+1}
• a proof about tiling with triominos
• the Nim game from section 11.10

We also had a visit from the Recursion Fairy.

The triominos proof is interested because there are many checkerboards of each size (depending on which square we remove from the board) and because we divide each big board into four smaller boards (not just one or two smaller objects).

The Nim game is interesting because we have to use the fact that the claim works for a smaller game, but we have very weak control over how much smaller this game is.