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