Divide a square into different parts This is a very interesting word problem that I came across in an old textbook of mine. So I know its got something to do with geometry, which perhaps yields the shortest, simplest proofs, but other than that, the textbook gave no hints really and I'm really not sure about how to approach it. (After a while of mindless fumbling, I came to the realisation that by square, the question meant an actual square drawing, not square as in $n^2$.)Any guidance hints or help would be truly greatly appreciated. Thanks in advance :) So anyway, here the problem goes:

Prove that for any $n > 5$, it is possible to divide a square into exactly $n$ parts, each of which is also a square. 

 A: By request, I'm spinning my comment out into an answer. For $n$ even, say $n=2k$, subdivide the square into a $k\times k$ grid of squares. I'll show it for $k=5$, because I think it's easier to visualize when everything renders as true squares rather than with $\dots$:
$$\begin{array}{|c|c|c|c|c|}
\hline
\,\,&\,\,&\,\,&\,\,&\,\, \\
\hline
& & & &  \\
\hline
& & & &   \\
\hline
& & & & \\
\hline
& & & & \\
\hline
\end{array}
$$
Now divide it into the top row of squares, the left column of squares, and everything else:
$$\begin{array}{|c|c c c c|}
\hline
\,\,&\,\,\,\,\mid &\,\,\mid &\,\,\mid& \\
\hline
\underline{\,\,\,}& & & &  \\
\underline{\,\,\,}& & & &  \\
\underline{\,\,\,}& & & &  \\
& & & &  \\\hline
\end{array}
$$
(Sorry for the horrible latex hack, but \multicolumn didn't work.) So we have $2k-1$ little squares and one big one, for a total of $2k=n$.
For $n$ odd, split one of the squares into four. (This leaves the "corner case" $n=7$, which I leave as an exercise for the interested reader :) 
A: Assume we start with a square with sides of length 1.  Proof by induction:
For n = 6, the square can be split into 1 square with sides of length 2/3 and 5 squares with sides of length 1/3.
For n = 7, the square can be split into 3 squares with sides of length 1/2 and 4 squares with sides of length 1/4. (i.e. split the original square into 4 smaller squares, then split one of the smaller squares into 4 even smaller squares).
For n = 8, split the square into one square with sides of length 3/4 and 7 squares with sides of length 1/4.
For n > 8, take the solution for n - 3, and split any one square into 4 smaller squares, adding 3 squares to the count.
