Derive the following identity $1^2+2^2+ \ldots + n^2 = \frac{n(n+1)(2n+1)}{6}$. 
Count the elements of the following set 
  $$A=\{(x,y,z): 1\leq x,y,z \leq n+1, z>\max\{x,y\}\}.
$$ 
  From this derive the following identity:
  $$1^2+2^2+ \ldots + n^2 = \frac{n(n+1)(2n+1)}{6}.$$
  In the same manner find the formula for $1^k + 2^k + \ldots + n^k$ for $k=3,4$.

It is easy to see that $|A| = 1^2 + 2^2 + \ldots + n^2$, since from the sum rule we have $$|A| = \sum_{i=0}^{n+1} |\{(x,y,i): 1\leq x,y,z \leq n+1, i> \max\{x,y\}\}| = \sum_{i=0}^{n+1} i^2$$ (as we can choose $x$ and $y$ in $i \times i$ ways for each $i$).
However I can't see why is $|A|$ equals $\dfrac{n(n+1)(2n+1)}{6}$.

One method is this: When n= 0, the sum is 0.  When n= 1, the sum is 1.  When n= 2, the sum is 1+ 4= 5.  When n= 3, the sum is 1+ 4+ 9= 14.  When n= 4 the sum is 1+ 4+ 9+ 16= 30.  When n= 5 the sum is 1+ 4+ 9+  16+ 25= 55, etc.
Obviously, at each step we are just adding the next square so the "first differences" are: n= 0, 1- 0= 1; n= 1, 5- 1= 4; n= 2, 14- 5= 9; n= 3, 30- 14= 16; n= 4, 55- 30= 25, etc.
The "second differences" are: n= 0, 4- 1= 3; n= 1, 9- 4= 5; n= 2, 16- 9= 7; n= 3, 25- 16= 9.
The "third differences" are:  n= 0, 5- 3= 2; n= 1, 7- 5= 2; n= 2, 9- 7= 2.
The third differences are the constant 2 so all succeeding differences are 0.  By "Newton's divided difference formula" the sequence is given by $a_n= 0+ 1(n)+ 3(n)(n-1)/2!+ 2(n)(n-1)(n-2)/3!= \frac{1}{6}\left(6n+ 9n^2- 9n+ 2n^3- 6n^2+ 4n\right)= \frac{1}{6}\left(2n^3+ 3n^2+ n\right)= \frac{1}{6}n(n+1)(2n+1)$.
As a check, when n= 1, that is $\frac{1}{6}(2+ 3+ 1)= 1$; when n= 2, that is $\frac{1}{6}(16+ 12+ 2)= 5$; when n= 3, that is $\frac{1}{6}(54+ 27+ 3)= 14$, etc.
