Question

Why couldn't I prove the hypothesis by simply putting one square in the center for Bill and the rest in the center? What am I missing ? http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/video-lectures/lecture-2-induction/ (starts at 59:00) - I apologize its the math course, not the CS one

Answer 1

it might be a math course, but mathematics majors usually don't take these courses. this belongs here. You should try to post it in math. im curious if they could answer.

Answer 2

can you post the question or draw it?

Answer 3

The problem is that doing that you are still left to prove that the quarter with bill's square remaining missing can be tiled.
So to do it that way he first proved a lemma that any \( 2^n \) square can be tiled with a corner block missing.

He did this by proving \( p(0) \) which is a trivial case, because it is a square with a single block which is also the corner, so it can be missing.
Then by assuming it is true for \( p(n) \) he proved for \( p(n+1) \) by dividing the square into quarters and removing 3 blocks from the square's center and one from the corner:

Now notice that the middle missing blocks can be filled with a tile, and you get a square with a corner block missing.. so the lemma is proved, because you can use this \(p(n+1)\) square as the quarters of \( p(n+2) \) and prove the same way.

Now he did pretty much what you said. he took the the corner block and moved to the center:

and said that since the quarters are each a square with a missing corner block, then by the lemma then can be each tiled and by filling 3 of these in the center you are left with one center block missing. done

Then he gave the much simpler proof for 'any missing block' and not just corner block, which is neat =)