How does this proof by induction works?

Question

Source: MIT OCW 6.042 by Tom Leighton, Lecture 2; Please skip to time 1:00:45.

In this question, the professor proves:

$2^n.2^n$ courtyard can be filled with tiles of L shaped (composed of 3 unit square tiles) having a free unit square tile free for Bill at the center is true for all $n \in N$

Failing to do so, he changes the technique to:

$2^n.2^n$ courtyard can be filled with tiles of L shaped (composed of 3 unit square tiles) having a free unit square tile free for Bill at the corner is true for all $n \in N$

But this technique cannot be extended to prove the initial proposition. So he takes a stronger technique:

$2^n.2^n$ courtyard can be filled with tiles of L shaped (composed of 3 unit square tiles) having a free unit square tile free for Bill at any position is true for all $n \in N$

---

I understand the idea behind taking stronger technique, and also understand the proof. I don't understand one thing.

I know that when you prove some proposition true you have to prove it for all cases. But in the above proof he fixed the positions of three blank squares, and only one is free. Like here blue, green and yellow are fixed and only red can be anywhere.

The total possibilities for four $4.4$ courtyards having one unit square missing, arranged in a big square of $8.8$ courtyard: $2^4.2^4.2^4.2^4 = 2^{16}$ possible layouts.

But the above proof fixes three squares so it becomes; $2^4+2^4+2^4+2^4 = 4.2^4 = 2^6$.

I'm thinking that proof like this and with this perspective it seems an incorrect proof to me. I know the proof is right, my approach is wrong, please tell me how does it work for every possibility, for example this.

Answer 1

Your question actually shows that you do not understand induction. I very strongly advise you to learn basic first-order logic, because that is the only way to truly understand induction. However, in the interim you should read this on induction and this on game semantics.

Once you fully understand those two posts, it should be clear what you have here:

Given any $2^n×2^n$ square grid with a missing unit square:
  If $n = 0$, then it is trivially tileable. So we are left with the case $n>0$.
  Thus the missing square is in one of the $4$ equal parts each of size $2^{n-1}×2^{n-1}$.
  We can remove $3$ appropriate centre squares so that each part has exactly one missing square.
  Note that those $3$ centre squares can be covered by an L-tile.
  If each of those $4$ parts can be L-tiled, then the whole grid can be L-tiled.
Therefore by induction the whole grid can be tiled.

Furthermore, the professor is incorrect that the corner version of the theorem cannot be used to prove the original proposition! Suppose you have proven the corner version. Then any square grid with size at least $2×2$ and all centre squares removed can be L-tiled (since each of the 4 parts can be L-tiled, by the corner version), and hence any square grid with size at least $2×2$ and one centre square removed can also be L-tiled.

Answer 2

Start with a $2^{n+1}\times 2^{n+1}$ courtyard with any unit square missing. Scale the courtyard down by a factor of $\frac 12$. Now you have a $2^{n}\times 2^{n}$ courtyard with some unit square having a defect in form of a half-unit square missing. By induction hypothesis, this $2^n\times 2^n$ courtyard can be tiled by L shapes leaving the defective unit square free. Now scale by a factor of $2$ back to the original situation. Replace the now big L shapes by four L shapes each. The defective square was scaled up to a $2\times 2$ square with the original missing unit square in one of its corners. This can be covered by a single L shape.