number of squares in a rectangle.

Given a rectangle of length a and width b(as shown in the figure).How many different squares of edge grater than 1 can be formed from using the cells inside .

For example if a=2,b=2 ,then the number of such squares is just 1.

-
Are the interior cells squares? – Jebruho Nov 4 '12 at 21:25
Also, check your spelling. – Jebruho Nov 4 '12 at 21:26
@Jebruho:Interior cells are squares. – g4ur4v Nov 4 '12 at 21:28
@WillHunting:a and b can be different. – g4ur4v Nov 4 '12 at 21:29

In general, given an $n \times k$ grid of squares, to find the number of rectangles you can form, you would turn your grid into an $n \times k$ multiplication table, put the values into each square (i.e., the $i$th row and $j$th column would contain $i \cdot j$), and then sum them all up. Proving that this holds is a nice exercise.

For your particular question, you are asked to find the number of squares in a $3 \times 3$ grid where each square has its sides greater than $1$. This is straightforward to figure out directly from your picture (how many $3 \times 3$ squares are there? how many $2 \times 2$ squares are there?) but the solution also becomes clear to anyone who proves the statement of the previous paragraph.

The number of $3 \times 3$ squares is $1$, which is $1 \cdot 1$; the number of $2 \times 2$ squares is $4$, which is $2 \cdot 2$. Thus, the total is $1 + 4 = 5$.

Incidentally, the number of $1 \times 1$ squares is $9$, which is $3 \cdot 3$. Note that $1, 4, 9$ are the entries of the diagonal in a $3 \times 3$ multiplication table. This is no coincidence!

Given an $n \times n$ multiplication table, to find the number of squares, just add up all the elements of the diagonal. The formula for the sum of the first $n$ squares, by the way, is $n(n+1)(2n+1)/6$, which you could look up online or prove by induction.

Since you want to exclude $1 \times 1$ squares, you would subtract $n^2$ from this sum, giving a final answer of $$S(n) = \frac{n(n+1)(2n+1)}{6} - n^2 = \frac{(n-1)n(2n-1)}{6}$$

Indeed, for $n = 3$, we find $S(3) = 5$ as desired.

-
:This is great for when a=b=n.What about when a is not equal to b? – g4ur4v Nov 4 '12 at 21:53
Try to prove the statement from the first paragraph and see what sort of insights that gives you. Also, for a semi-related question, check out: math.stackexchange.com/questions/226983/… – Benjamin Dickman Nov 4 '12 at 21:58

Without loss of generality we may assume that that the width $b$ is $\ge$ to the height $a$. Note that there are $b+1$ vertical lines and $a+1$ horizontal lines in the picture.

If $a\ge 2$, the number of $2\times 2$ squares is $(a-1)(b-1)$. This is because the top left corner of a $2\times 2$ square can be any corner that is not in the last two columns or the last two rows.

If $a\ge 3$, the number of $3\times 3$ squares is $(a-2)(b-2)$. This is because the top left corner of a $3\times 3$ square can be any corner which is not in the last three columns or the last three rows.

If $a\ge 4$, the number of $4\times 4$ squares is $(a-3)(b-3)$.

Continue. Finally, the number of $a\times a$ squares is (a-(a-1))(b-(a-1))$. Add up. To get a "nice" expression for the sum, note that $$(a-k)(b-k)=ab-k(a+b)+k^2.\tag{1}$$ When we add up the expressions in$(1)$, we get$a-1$terms with value$ab$, for a total of$(a-1)ab$. The "middle" terms add up to$-(a+b)(1+2+\cdots+(a-1))$. The sum is$-(a+b)\dfrac{(a-1)a}{2}$. Finally, we need$1^2+2^2+\cdots +(a-1)^2$. By the usual formula for the sum of consecutive squares, this is equal to$\dfrac{(a-1)(a)(2a-1)}{6}\$.

-