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}$.

On the one hand, $|A|=\sum_{i=1}^n i^2$.
On the other hand, we can also count the elements of $A$ by grouping them according to the order of $x$ and $y$.


*

*when $x\neq y$ means that $x<y<z$ or $y<x<z$, so it contributes $2\binom{n+1}{3}$.

*when $x=y$, the amount of $(x,x,z)$ is $\binom{n+1}{2}$.


So $\sum_{i=1}^n i^2=|A|=2\binom{n+1}{3}+\binom{n+1}{2}=\frac{n(n+1)(2n+1)}{6}$
