2 added 11 characters in body

The first example of an explanatory proof by induction that comes to mind is the solution to the following problem which comes originates (to me ultimately my best knowledge) from Art Benjamin.

By a triomino I will mean an "L-shaped" union of 3 unit squares.

Claim: A $2^n \times 2^n$ grid of unit squares with one square removed can always be covered by triominos.

Proof:

Base case: if $n=1$ then we need to cover a $2 \times 2$ grid with one square removed by triominos. THat is, we need to cover a triomino by triominos. So we're good here.

Induction step: Assume that we can cover any $2^n$ by $2^n$ grid of squares with one square removed by triominos and suppose that we are presented with a $2^{n+1} \times 2^{n+1}$ grid of unit squares.

Separate this into a $2 \times 2$ grid of $2^n \times 2^n$ grids of squares one of which has one square removed. At the place where the four corners of these grids meet, place a triomino in such a way that it covers the corner square of each of the three $2^n \times 2^n$ grids without a square already having been removed.

Now what remains to be covered is the union of four $2^n \times 2^n$ grids of squares each with one square removed, so by the induction hypothesis we can cover it with triominos.

1

The first example of an explanatory proof by induction that comes to mind is the solution to the following problem which comes to me ultimately from Art Benjamin.

By a triomino I will mean an "L-shaped" union of 3 unit squares.

Claim: A $2^n \times 2^n$ grid of unit squares with one square removed can always be covered by triominos.

Proof:

Base case: if $n=1$ then we need to cover a $2 \times 2$ grid with one square removed by triominos. THat is, we need to cover a triomino by triominos. So we're good here.

Induction step: Assume that we can cover any $2^n$ by $2^n$ grid of squares with one square removed by triominos and suppose that we are presented with a $2^{n+1} \times 2^{n+1}$ grid of unit squares.

Separate this into a $2 \times 2$ grid of $2^n \times 2^n$ grids of squares one of which has one square removed. At the place where the four corners of these grids meet, place a triomino in such a way that it covers the corner square of each of the three $2^n \times 2^n$ grids without a square already having been removed.

Now what remains to be covered is the union of four $2^n \times 2^n$ grids of squares each with one square removed, so by the induction hypothesis we can cover it with triominos.