Proof of square tesselation with trominos

For each natural number n, consider a square consisting of 2^(2n) smaller squares (i.e., a 2^n × 2^n square). If any one of the smaller squares is removed from the large square (not necessarily from the corner), then the resulting region can be completely covered by trominos (each made up of three small squares of the same size as the small squares in the region) in such a way that the trominos do not overlap.

Yes, for every natural number $n$, if we remove any one of the $2^{2n}$ smaller squares from a $2^n \times 2^n$ square, it is always possible to tile the remaining region using only L-shaped trominos (three connected unit squares forming an "L") without overlap or gaps.

---

✅ Key Concepts:

• A tromino is an L-shaped tile made up of 3 connected unit squares.
• We are working with a $2^n \times 2^n$ square, which contains $2^{2n}$ unit squares.
• One square is removed, leaving $2^{2n} - 1$ unit squares to be tiled.

---

🧠 The Proof (by induction):

Base case: $n = 1$

• A $2^1 \times 2^1 = 2 \times 2$ square has 4 unit squares.
• Removing one square leaves 3 squares — which perfectly matches the shape of a tromino.
• ✅ The base case holds.

---

Inductive step:

Assume the statement holds for some $n = k$: Any $2^k \times 2^k$ square with one square removed can be tiled with trominos.

Now consider a $2^{k+1} \times 2^{k+1}$ square.

• This square can be divided into four $2^k \times 2^k$ quadrants.
• The removed square lies in one of these four quadrants.
• By the inductive hypothesis, we can tile the affected quadrant after placing a tromino at the center of the full square that covers one square in each of the other three quadrants, near the center.
• Now each of the four quadrants has one square missing, so each can be tiled by the inductive hypothesis.

✅ This completes the inductive step.

---

📌 Conclusion:

By mathematical induction, any $2^n \times 2^n$ square with one unit square removed can always be tiled completely with L-shaped trominos.

---

Would you like a visual demonstration or code to simulate this tiling?