# 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 greater than 1 can be formed 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? Nov 4, 2012 at 21:25
• Also, check your spelling. Nov 4, 2012 at 21:26
• @Jebruho:Interior cells are squares. Nov 4, 2012 at 21:28
• @WillHunting:a and b can be different. Nov 4, 2012 at 21:29

## 3 Answers

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? Nov 4, 2012 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/… Nov 4, 2012 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}$. In an$n\times p$rectangle, the number of rectangles that can be formed is$\frac{np}{4(n+1)(p+1)}$and the number of squares that can be formed is$\sum_{r=1}^n (n+1-r)(p+1-r)$. • Why$n \times p$instead of$a \times b\$ as in the question? Aug 21, 2016 at 7:55
• While this answer gives a little bit of an idea how to solve the question, it does not contain enough detail to merit answering an almost 4-year old question. And it is not formatted properly. Aug 21, 2016 at 7:56