# Given an $n \times n$ grid, how many squares exist?

How many squares exist in an $n \times n$ grid? There are obviously $n^2$ small squares, and $4$ squares of size $(n-1) \times (n-1)$.

How can I go about counting the number of squares of each size?

• Can you count the number of $m \times m$ squares, for any $1 \le m \le n$? – arkeet Sep 26 '16 at 16:07
• $\Sigma i^2 = \dfrac{n(n+1)(2n+2)}{6}$ – Shailesh Sep 26 '16 at 16:22
• Continue your logic. On one side of the grid there are n segments of length 1. So n^2 1x1 squares. There are n-1 segments of length 2. So (n-1)(n-1) 2x2 squares. There are n - i+i segments of length i. so (n-i+i)(n-i+1) ixi squares. So $\sum_{i=0}^{n-1}(n-i)^2 = \sum_{k=1}^n k^2$ squares total. – fleablood Sep 26 '16 at 17:25

Another way to view this: for each size, there is one square that you move inside the larger one.

How much can it move? A square of size $k\times k$ inside a square of size $n\times n$ has $n-k+1$ possible positions in each direction (up-down and left-right): consider the position of the top left corner for instance. Hence there are $(n-k+1)^2$ such squares.

Can you finish from here?

• Now I sum over k. This collapses to a sum of squared integers not greater than n. Thanks! – Demetri Pananos Sep 26 '16 at 16:32

NOTE:

For $n\times n$ grid the answer is $n^2+(n-1)^2+(n-2)^2+.....+1^2$

So, the answer is $$\frac{n(n+1)(2n+1)}{6}$$

Another way of counting:

For each $(i, j, k)$ with $1 \le i, j \le n$ and $0 \le k \le \min(n-i, n-j)$ there is a square with upper left corner at $(i, j)$ and lower right corner at $(i+k, j+k)$.

Therefore the total is

$\begin{array}\\ s(n) &=\sum_{i=1}^n \sum_{j=1}^n (1+\min(n-i, n-j))\\ &=\sum_{i=0}^{n-1} \sum_{j=0}^{n-1} (1+\min(i, j))\\ &=n^2+\sum_{i=0}^{n-1} \sum_{j=0}^{n-1} \min(i, j)\\ &=n^2+\sum_{i=0}^{n-1} (\sum_{j=0}^{i-1} \min(i, j)+\sum_{j=i} \min(i, j)+\sum_{j=i+1}^{n-1} \min(i, j))\\ &=n^2+\sum_{i=0}^{n-1} (\sum_{j=0}^{i-1} j+i+\sum_{j=i+1}^{n-1} i)\\ &=n^2+\sum_{i=0}^{n-1} (\frac12i(i-1)+i+i(n-1-(i+1)+1))\\ &=n^2+\sum_{i=0}^{n-1} (\binom{i}{2}+i+i(n-i-1))\\ &=n^2+\binom{n}{3}+\frac12 n(n-1)+\sum_{i=0}^{n-1} (ni-i(i+1))\\ &=n^2+\binom{n}{3}+\frac12 n(n-1)+\frac12 n^2(n-1)-\sum_{i=1}^{n} i(i-1)\\ &=n^2+\binom{n}{3}+\frac12 n(n-1)+\frac12 n^2(n-1)-2\binom{n+1}{3}\\ &=\frac13(n+1)n(n-1)\\ \end{array}$

Let the vertices of the $n \times n$ grid by $\{(x,y)| 0\le x \le n; 0 \le y \le n\}$.

(Is that what an $n \times n$ grid is? A $1 \times 1$ has $4$ vertices and an $n \times n$ grid has $(n+1)^2$ vertices? Or is a $1 \times 1$ grid a single point? I'm assuming the former.)

A $k \times k$ square will have an lower left hand vertex as $(x,y)$ and a upper right hand vertex at $(x+k, y+k)$ with the stipulation $0 \le x; 0 \le y; x+k \le n; y+k \le n$ or in other words: $0 \le x \le n-k; 0 \le y \le n-k$.

There are $n-k+1$ possible options for $x$ and $n-k+1$ options for $y$ so there $(n-k+1)^2$ $k\times k$ squares.

So the total number of squares is $\sum{k=1}^n(n-k+1)^2$. Let $j = n-k+1$ and we have #squares = $\sum_{j = n;j--}^1j^2 = \sum_{j=1}^n j^2 = \frac{n(n+1)(2n+1)}6$

Or to put it more simply.... A $k \times k$ square has a side of length $k$. There are $n-(k-1)$ ways to choose this side from the grid that is $n$ long so for squares of lengths $1,2, ...., n$ there are $n, n-1....., 1$ way to choose the horizontal side and $n, n-1,...., 1$ ways to choose the vertical sides. So there are $n^2, (n-1)^2,....., 1^2$ possible $1\times 1, 2\times 2, ...,n \times n$ squares. So there are $\sum k^2 = \frac{n(n+1)(2n+1)}6$ total squares.