Question 110283: 7X7 square consisting of 49 1x1 squares. How many total squares can be made (1x1, 2x2, 3x3, etc)
Answer by wgunther(43)   (Show Source):
You can put this solution on YOUR website! Helps to draw a picture. Honestly, I'm not sure what kind of class this is for, but I'm going to assume you have some idea of induction or recursion. Let's find an inductive relationship.
1x1: 1 way to make this
2x2: you can use 4 1x1 tiles, or 1 2x2 tile, 2 ways
3x3: you can use 9 1x1 tiles (1 way), or 5 1x1's and a 2x2 (4 ways as the 2x2 can be in the upper left, upper right, etc), or a 3x3 (1 way). 1+1+4(2-1)=6 ways
4x4: 16 1x1 (1 way) or you can have 7 1x1 and a 3x3 (4 ways, but there are 6 ways to do a 3x3, one of which with all 1x1's so we have to omit that one, so thats 4*(6-1) ways, 20 ways), or a 4x4 (1 way) 1+1+4(6-1)=22 ways
So, we conjecture that the number of ways to make a NxN is equal to 2+4(# of ways to make a (N-1)x(N-1)-1). We have to prove it inductivly but I'll leave that out. We can find a forumla recursivly. In this case recursion tells us the forumula is a geometric series, and the forumla is given by  honestly, I'm not sure this is right, I'm not going to lie, but I tried =) so 
|
|
|
