Consider the set of points $$S=\{(x,y):x,y\text{ are non-negative integers}\le n\}$$ Find the number of squares that can be formed with vertices belonging to $S$ and sides parallel to the axes.
Find The Number of Squares
3 Answers
It’s probably easiest to count them by size. A $1\times 1$ square can have its lower lefthand corner at any $\langle x,y\rangle\in S$ such that $x,y<n$, so there are $n^2$ such small squares. A $2\times 2$ square must have its lower lefthand corner at some $\langle x,y\rangle\in S$ such that $x,y<n-1$; there are $(n-1)^2$ of these. Proceeding in the same way, we see that there $k\times k$ squares must have their lower lefthand corners at points $\langle x,y\rangle\in S$ such that $x,y<n-k+1$, so there are $(n-k+1)^2$ of them. When $k=n$, the largest possible case, this is $1^2$, so the total is $$\sum_{k=1}^nk^2=\frac16n(n+1)(2n+1)\;.$$
I will need some drawing help. For an $n$ that is small but not too small, put dots at the $(n+1)\times (n+1)$ gridpoints with coordinates $(x,y)$, where $0\le x,y\le n$. Something like $n=5$ is good enough.
Now draw the diagonals that go in the Northwest to Southeast direction. The diagonal closest to the origin has $2$ gridpoints on it, the next diagonal has $3$ gridpoints, the next has $4$, and so on. This continues until we hit the main diagonal, which has $n+1$ gridpoints. As we go further up, the number of gridpoints decreases, to $n$, then $n-1$, and so on until our last diagonal, which has $2$ gridpoints.
Take any of these diagonals, and pick two gridpoints on it. Then there is a unique square which has these two points as its Northwest and Southeast corners. As we consider all of our diagonals, and all the ways to choose $2$ points, we produce in this way all possible squares, in exactly one way. It follows that the total number of squares is $$\binom{2}{2}+\binom{3}{2}+\cdots +\binom{n}{2}+\binom{n+1}{2}+\binom{n}{2}+\cdots + \binom{3}{2}+\binom{2}{2}.$$ Nice, but not really simple. We now proceed to simplify. There is the middle term $\dbinom{n+1}{2}$ plus twice the quantity $$\binom{2}{2}+\binom{3}{2}+\cdots +\binom{n}{2}.\tag{$\ast$}$$ We claim that the quantity $(\ast)$ is equal to $\dbinom{n+1}{3}$.
For $\dbinom{n+1}{3}$ is the number of ways of picking $3$ numbers from the $n+1$ numbers $0, 1, 2,\dots,n$. When we pick $3$ numbers, the smallest of the numbers picked could be $n-2$. Then the other two numbers can be picked in $\binom{2}{2}$ ways (well, $1$ way). Or else the smallest number picked could be $n-3$. Then the other two can be picked in $\binom{3}{2}$ ways. Or else the smallest is $n-4$, in which case the other two can be picked in $\binom{4}{2}$ ways. Continue on down. Finally, the smallest of the $3$ numbers picked could be $0$, in which case the other two can be picked in $\binom{n}{2}$ ways. We have proved that $$\binom{2}{2}+\binom{3}{2}+\cdots +\binom{n}{2}=\binom{n+1}{3}.\tag{$\ast\ast$}$$ Now put things together. The total number of squares is therefore $$\binom{n+1}{2}+2\binom{n+1}{3}.$$
Remark: Now for the interesting part! In the posted solutions, it was shown that the number of squares is equal to $$1^2+2^2+3^2+\cdots +n^2.$$ We conclude that $$1^2+2^2+3^2+\cdots +n^2=\binom{n+1}{2}+2\binom{n+1}{3}.$$ The expression on the right looks pretty nice as is. But if we really want to, we can expand it as $$\frac{(n+1)(n)}{2}+2\frac{(n+1)(n)(n-1)}{3!}.$$ A little simplification (bring to a common denominator, factor out the common factors $n$ and $n+1$) gives us to the more familiar expression $$\frac{n(n+1)(2n+1)}{6}.$$ So by counting the number of squares in a grid in two different ways, we can obtain a closed form formula for the sum of the first $n$ perfect squares.
Sum of $i^2$, i going from 1 to n = $n(n+1)(2n+1)/6$.
Reason: Number of such squares of edge length $n + 1 - i$ is $i^2$.To see why, just keep track of the possible locations the bottom left corner of such a square can have.
-
0could you please explain a little? – 2012-04-16
-
1I had edited the answer to give more details, I hope it is clear now. – 2012-04-16
-
0@Makuasi This is ironic, given the succinctness of your question. It is good and encouraged that you provide some of your work on the problem so that it doesn't look like you want someone else to do your work. – 2012-04-16
-
1The number of retangles is ${\binom{n+1}{2}}^2 = \frac{n^2 (n+1)^2}{4}$, for reference. – 2012-04-16