# Extending a proof to squares from an m*n grid

From this page it can be shown that the number of possible rectangles in and m*n grid can be found by first choosing $2$ lines from a possible $m+1$ to form the vertical sides of the rectangle, and then $2$ from the $n+1$ horizontal sides, to give ${{m+1} \choose {2}}*{{n+1} \choose {2}}$ rectangles.

I want to extend this proof to cover only squares

I have tried choosing $2$ from ${m+1}$ for one set of sides, as a square can be formed with any two lines, but I am having trouble on how many choices there are for the remaining sides. If the first two sides are beside each other, then the last two can be any two sides that are beside each other, so there are so n choices, but after that I get lost.

The formula given on the page using a different approach is $$\frac {{n}{(2n+1)}{(n+1)}}{6}$$ or the sum of squares when m = n

• Do you understand why the formula for choosing a squares from a square works? The case of choosing squares from a rectangle can easily be derived from this Commented Sep 10, 2015 at 19:21
• Note: the formula for squares is only for the special case $m=n$. Commented Sep 10, 2015 at 19:21
• Let $m\le n$. Count the number of $1\times 1$ squares, $2\times 2$ squares, and so on up to $m\times m$ and add up. The "sum of consevutive squares" formula will be useful. Commented Sep 10, 2015 at 19:24
• @AndréNicolas I understand that proof, my question is where it is possible to prove this by choosing sides for the squares Commented Sep 10, 2015 at 19:26
• Direct use of the choosing parallel lines idea is not useful. If $m\le n$ there are indeed $\binom{m+1}{2}$ ways to chose $2$ parallel sides. But some choices, like the two lines close together, give many squares, and some choices give few squares. Commented Sep 10, 2015 at 19:30

If you are ok with writing summations, and expressing your formla in terms of sum of multiplied expressions, then your're basically already there. If $m \leq n$ then you can write down an expression for how many $k \times k$ squares you can form by independently choosing the two indepentdent pairs of dividing lines for the horizontal and vertical dividing lines. Once you have this summation formula, then the only thing left to (possibly) do is see if you can reduce your summation formula to a more closed form solution.
You don't state your question carefully. It sounds like you are trying to determine the number of squares in an $m \times n$ grid (so $(m+1) \times (n+1)$ gridlines). I would suggest you count the sizes separately and add them up. Let us assume $m \le n$, so the largest square you can form is $(m+1) \times (m+1)$. There are $mn$ squares of size $1$, $(m-1)(n-1)$ squares of size $2$, down to $1\cdot (n-m+1)$ squares of size $m+1$, so the total is $$\sum_{i=1}^m(m+1-i)(n+1-i)$$ Now distribute out the terms and you get a sum of terms that do not depend on $i$, a sum that depends on $i^1$ and a sum that depends on $i^2$