# Induction problem 3

### Solution

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.