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

We can prove it by induction:
Step 1: check it for base case (n=1)
If we replace $n$ by one, we get: $$ 1^2=\frac{1\times 2 \times 3}{6}$$
which holds $\checkmark$
Step 2: assume it is true for $n=k$ and check if holds for $n=k+1$
If it holds for $n=k$, then we have:
$$1^2+2^2+…+k^2=\frac{k(k+1)(2k+1)}{6}$$
Now we show it also holds for $n=k+1$. By replacing $n$ by $k+1$ we should show:
$$1^2+2^2+…+(k+1)^2=\frac{(k+1)(k+2)(2(k+1)+1)}{6}$$
or
$$1^2+2^2+…+k^2+(k+1)^2=\frac{(k+1)(k+2)(2k+3)}{6}$$
(I want to skip some parts here, but its straight forward). Now the right hand side can be reshaped as:
$$\frac{(k+1)(k+2)(2k+3)}{6}=\frac{k(k+1)(2k+1)}{6}+(k+1)^2$$
which proves it holds for $n=k+1$ if it holds for $n=k$ $\checkmark$ 
This completes the proof. 
