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.