Derive the following identity $1^2+2^2+ \ldots + n^2 = \frac{n(n+1)(2n+1)}{6}$.

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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.