Find The Number of Squares 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.
 A: 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&ltn$, 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&ltn-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&ltn-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)\;.$$
A: 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. 
A: 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.
