Prove: Square Can Be Partitioned into n Smaller Squares for n > 14

[CoachZ]

Homework Statement

For n>14 such that n is an integer, prove that a square can be partitioned into n smaller squares...

Homework Equations

None...

The Attempt at a Solution

I was thinking this would be somewhat of an induction proof because we are working our way up to n. So far, I've found when n = 15, n = 17, but somehow n = 16 is eluding me at the moment. I'm just trying to see what it would look like if I were to do this visually, however my assumption is that this has to deal with modulo 3 in some form or another. How this works into a proof is also something that is eluding me. Any suggestions would be warmly welcomed!

 

[CompuChip]

I'm sorry I can't be of much help, but at first sight a proof by induction seems impossible. Because suppose you have shown that if it is possible for n, then it can also be done for n + 1.
Clearly, for n = 4 the statement is true (or even for n = 1, if you want). Also, what do you mean by "partition into smaller squares"? Does that count all squares? For example, when you draw a 3x3 grid in the square, does that give 9 squares? Or does that give 9 (1x1) squares + 4 (2x2) squares = 13 in total?
Also, can you post an image for n = 15, just to get the problem clear?