1. ## A 'squareish' question

Hi everyone. So I have a question here. Find the number of squares contained in an n x n square array, where n is larger or equal to 2.

Ok so my solution: For 1x1 Square array, no of squares=1

Then keep on doing till a pattern is formed, which is $\displaystyle r squared$.

However, when I flipped to the solutions, they proposed an alternative method which I do not understand. They examined 2 x 2 squares and noted that the bottom-left hand corner of each square is unique. If you consider the (n x n) array as (n+1)(n+1) grid (why????) with both x and y coordinates such that x=0,1,2,.....,n-2 (????) repeat for y. The number of points equals (n-1)(n-1) (????)and this the number of 2x2 squares is (n-1)(n-1).

More generally, number of r x r squares is (n-r+1)(n-r+1).

Actually I dont really understand the method which the book wrote and had trouble visualizing it. Any helps?

Thanks.

2. Originally Posted by qazxsw11111
Hi everyone. So I have a question here. Find the number of squares contained in an n x n square array, where n is larger or equal to 2.

Ok so my solution: For 1x1 Square array, no of squares=1

Then keep on doing till a pattern is formed, which is $\displaystyle r squared$.

However, when I flipped to the solutions, they proposed an alternative method which I do not understand. They examined 2 x 2 squares and noted that the bottom-left hand corner of each square is unique. If you consider the (n x n) array as (n+1)(n+1) grid (why????) with both x and y coordinates such that x=0,1,2,.....,n-2 (????) repeat for y. The number of points equals (n-1)(n-1) (????)and this the number of 2x2 squares is (n-1)(n-1).

More generally, number of r x r squares is (n-r+1)(n-r+1).

Actually I dont really understand the method which the book wrote and had trouble visualizing it. Any helps?

Thanks.
Suppose you know the number of squares N(n) formed on an nxn array now add a border one square wide around the top and right hand edges to give an (n+1)x(n+1) array.

Every square on the (n+1)x(n+1) array is either a square on the nxn array or has a corner on the border just added. Count these new squares C(n+1) with a corner on the border, and that will give you a recurrence:

N(n+1)=N(n)+C(n+1)

which you solve.

CB