Proof by induction on n.

Base Cases:Suppose that our square has sides of length p.

- n=6
- The square can be subdivided into 6 smaller squares by making one square with side length of \(\frac{2p}{3}\) situated in the lower left corner. The other 5 squares with side length \(\frac{p}{3}\) can fill the L shaped corridor that is left over.
- n=7
- The square can be subdivided into 7 smaller by cutting a square into 4 equal squares, then cutting one of those smaller squares into 4 smaller but identical squares, producing 7.
- n=8
- The square can be subdivided into 8 smaller squares by making one square with side length of \(\frac{3p}{4}\) situated in the lower left corner. The other 7 squares with side length \(\frac{p}{4}\) can fill the L shaped corridor that is left over.
6 squares 7 squares 8 squares ________ ------------- ------------- |__|__|__| | | | | | | | | | | |__| ------- | ------------- |_____|__| | | | | | | | ------------- | ---- | | | | | | | | | | ---- | | | | | | ------------- -------------

Induction hypothesis:Suppose that the square can be divided into n smaller squares, for \(n = 6,7,\ldots,k\) (where k is an integer \(\ge 8\)).Rest of inductive step:We need to show how to divide up the square into k+1 smaller squares.First, divide the square into four equal subsquares. Pick one of these smaller squares. By the inductive hypothesis, this smaller square can be further subdivided into \(k+1-3\) subsquares. The total number of squares is now \((k+1-3) + 3 = k+1\) subsquares. So we've divided our original big square into \(k+1\) smaller squares, which is what we needed to do.

## Alternate version of inductive step

Here's another way to do the inductive step. It uses the same tricks, but applied in the opposite order.

Rest of inductive step:We need to show how to divide up the square into k+1 smaller squares.Since \( k \ge 8\), \(k+1-3 = k-2 \ge 6\). So \(k+1-3\) lies in the range of values covered by the inductive hypothesis. So, by the inductive hypothesis, it is possible to divide the square into \(k+1-3\) smaller squares. Pick one of these smaller squares and divide it into four equal squares. This increases the total number of small squares by 3, producing a division of our original big square into \(k+1\) smaller squares. This is what we needed to show.