1
$\begingroup$

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.

3 Answers 3

4

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, 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; 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, 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)\;.$

5

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.

4

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.

  • 1
    The number of retangles is ${\binom{n+1}{2}}^2 = \frac{n^2 (n+1)^2}{4}$, for reference.2012-04-16