Vtyjkyuk

Count the elements of the following set
$$A=(x,y,z): 1leq x,y,z leq n+1, z>maxx,y.
$$
From this derive the following identity:
$$1^2+2^2+ ldots + n^2 = fracn(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): 1leq x,y,z leq n+1, i> maxx,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 $dfracn(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 $xneq y$ means that $x<y<z$ or $y<x<z$, so it contributes $2binomn+13$.


• when $x=y$, the amount of $(x,x,z)$ is $binomn+12$.

So $sum_i=1^n i^2=|A|=2binomn+13+binomn+12=fracn(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=frac1times 2 times 36$$
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=frack(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=frack(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.

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!= frac16left(6n+ 9n^2- 9n+ 2n^3- 6n^2+ 4nright)= frac16left(2n^3+ 3n^2+ nright)= frac16n(n+1)(2n+1)$.

As a check, when n= 1, that is $frac16(2+ 3+ 1)= 1$; when n= 2, that is $frac16(16+ 12+ 2)= 5$; when n= 3, that is $frac16(54+ 27+ 3)= 14$, etc.