Exercise 29.

Given a square, you can cut the square into smaller squares by cutting along lines parallel to the sides of the original square (these lines do not need to travel the entire side length of the original square). For example, by cutting along the lines below, you will divide a square into 6 smaller squares:

$One large square with five squares of half the side length wrapping around the top and right side, forming an even larger square.$

Prove, using strong induction, that it is possible to cut a square into $n$ smaller squares for any $n \ge 6\text{.}$

Hint.