Induction and Recursive Structure in Puzzles

A puzzle stated for "n coins" or "n people" or "a chessboard of any size" is rarely meant to be solved from scratch at every size. If solving the size-$n$ version can be reduced to solving the size-$(n-1)$ version plus one small, fixed piece of extra work, you only need two things: the smallest case, solved directly, and the reduction step, applied over and over. That pair is a complete proof for every $n$.

Worked example: tiling a deficient board with L-trominoes

A $2^n \times 2^n$ board has one square removed, anywhere on the board. Prove it can always be tiled exactly by L-shaped trominoes (three squares in an L), each covering three cells.

Base case, $n=1$. A $2\times2$ board with one square removed has exactly three squares left, and those three squares always form an L-shape. One tromino tiles it. Done.

The reduction. Assume the claim is true for every $2^{n-1}\times2^{n-1}$ board with one square missing. Take a $2^n\times2^n$ board with one square missing, and cut it into four quadrants, each $2^{n-1}\times2^{n-1}$. One quadrant already contains the missing square. Place a single tromino at the very centre of the whole board, covering exactly one cell from each of the other three quadrants. Now all four quadrants have exactly one square "missing" — the original hole in one, and one tromino cell each in the other three. By the assumption, each quadrant can be tiled on its own. Combine the four tilings and the one centre tromino, and the whole board is tiled.

The same shape solves the Tower of Hanoi (moving $n$ disks reduces to moving $n-1$ disks twice, plus one move of the largest disk), and "prove a straight line always splits the plane into at most $\binom{n}{2}+n+1$ regions with $n$ lines" (adding the $n$-th line to an $(n-1)$-line arrangement crosses at most $n-1$ existing lines, adding at most $n$ new regions).

Sizing algorithms lean on the identical habit: a recursive backtest or a divide-and-conquer routine is trusted once its base case and its recursive step are each verified, not because every intermediate size was tested by hand.