Arithmetic progression problem

**xcluded** · December 10th 2009, 12:28 AM

Hi , i'm not sure how my lecturer got this. may i know what he did in between to derive this ?

$1^2 + 2^2 + .... + n^2$

$= (\frac{n}{6})(n+1)(2n+1)$

thanks

**janvdl** · December 10th 2009, 12:44 AM

Prove by induction.

For n = 1:

$1^2=1 \times \frac{(1)(1+1)(2 \times 1+1)}{6} = 1 \rightarrow$ true for $n = 1$

Now let n = k:

$1^2+2^2+...+k^2=\frac{k(k+1)(2k+1)}{6}$

We want to prove it for n = k + 1:

$1^2+2^2+...+k^2+(k+1)^2=\frac{(k+1)(k+2)(2(k+1)+1) }{6}$

We already have:

$1^2+2^2+...+k^2=\frac{k(k+1)(2k+1)}{6}$

So:

$\frac{k(k+1)(2k+1)}{6} + (k+1)^2 = \frac{(k+1)(k+2)(2(k+1)+1)}{6}$

Divide by $k+1$ and multiply by $6$

$k(2k+1) + 6(k+1) = (k+2)(2(k+1)+1)$

$2k^2+7k+6=2k^2+7k+6 \rightarrow$ true $\forall k$

**Soroban** · December 10th 2009, 04:20 AM

Hello, xcluded!

Are you sure he derived it himself?
It takes quite a bit of work . . .

$1^2 + 2^2 + \hdots + n^2 \;=\;\frac{n(n+1)(2n+1)}{6}$

We have: . $f(n) \;=\;1^2+2^2+3^2 + \hdots + n^2$

The first few values: . $f(1) = 1,\;f(2) = 5,\;f(3) = 14,\;f(4) = 30,\; f(5) = 55,\;f(6) = 81,\;\hdots$

Take the differences of consecutive terms,
. . then take differences of the differences, etc.

. . $\begin{array}{ccccccccccccc}\text {Sequence} & 1 && 5 && 14 && 30 && 55 && 81 \\ \text{1st diff.} && 4 && 9 && 16 && 25 && 36 \\ \text{2nd diff.} &&& 5 && 7 && 9 && 11 \\ \text{3rd diff.} &&&& 2 && 2 && 2 \end{array}$

The 3rd differences are constant.
Hence, the generating function is of the 3rd degree . . . a cubic.

The general cubic is: . $f(n) \:=\:an^3 + bn^2 + cn + d$

To determine $a,b,c,d$ , we use the first four terms of the sequence
. . and construct a system of equations.

. . . $\begin{array}{cccccccc}f(1) = 1: & a + b + c + d &=& 1 & [1] \\ f(2) = 5: & 8a + 4b + 2c + d &=& 5 & [2] \\ f(3) = 14: & 27a + 9b + 3c + d &=& 14 & [3] \\ f(4) = 30: & 64a + 16b + 4c + d &=& 30 & [4] \end{array}$

. . $\begin{array}{ccccccc} \text{Subtract [2] - [1]} && 7a + 3b + c &=& 4 & [5] \\ \text{Subtract [3] - [2]} && 19a + 5b + c &=& 9 & [6] \\ \text{Subtract [4] - [3]} && 37a + 7b + c &=& 16 & [7] \end{array}$

. . $\begin{array}{ccccccc} \text{Subtract [6] - [5]} && 12a + 2b &=& 5 & [8] \\ \text{Subtract [7] - [6]} && 18a + 2b &=& 7 & [9] \end{array}$

. . $\begin{array}{ccccccc} \text{Subtract [9] - [8]} && 6a \:=\:2 & \Rightarrow &\boxed{ a \:=\:\tfrac{1}{3}} \end{array}$

Substitute into [8]: . $12\left(\tfrac{1}{3}\right) + 2b \:=\:5 \quad\Rightarrow\quad\boxed{ b \:=\:\tfrac{1}{2}}$

Substitute into [5]: . $7\left(\tfrac{1}{3}\right) + 3\left(\tfrac{1}{2}\right) + c \:=\:4 \quad\Rightarrow\quad\boxed{ c \:=\:\tfrac{1}{6}}$

Substitute into [1]: . $\tfrac{1}{3} + \tfrac{1}{2} + \tfrac{1}{6} + d \:=\:1 \quad\Rightarrow\quad\boxed{ d \:=\:0}$

Hence: . $f(n) \:=\:\tfrac{1}{3}n^3 + \tfrac{1}{2}n^2 + \tfrac{1}{6}n \;=\;\tfrac{1}{6}n(2n^2+3n+1)$

. . Therefore: . $f(n) \;=\;\frac{n(n+1)(2n+1)}{6}$

**HallsofIvy** · December 10th 2009, 04:35 AM

janvdl proved it. To derive it, you can use "Newton's divided difference formula". If You make a list of values a(n), then subtract each value from the next, $\Delta(n)= a(n+1)- a(n)$ (That's the "difference". The "divided" part would be dividing by the distance between succesive indices which, here, is 1.) Form the "second difference" by subtracting each difference from the next, $\Delta^2(n)= \Delta(n+1)- \Delta(n)$ . Form the "third difference" similarly, etc. If you stop with the "kth difference", then a(n) is approximated by $a(0)+ \Delta(0)n+ \Delta^2(0)/2 n(n-1)+ \cdot\cdot\cdot+ \Delta^k(0)/k! n(n-1)(n-2)\cdot\cdot\cdot(n-k+1)$ . (That should remind you of the Taylor polynomials.)

If a(n) is a polynomial, that "kth difference" will eventually be all 0 and you get an exact polynomial expression for a(n).

For this problem, when n= 1, that sum is just $1^2= 1$ , when n= 2, it is $1^2+ 2^2= 5$ , when n= 3, it is $1^2+ 2^2+ 3^2= 14$ , etc. I am going to add a(0)= 0 for simplicity. Taking differences, second differences, etc., we get
$\begin{array}{ccccc}a(n) & \Delta(n) & \Delta^2(n) & \Delta^3(n) & \Delta^4(n) \\ 0 & 1 & 3 & 2 & 0\\ 1 & 4 & 5 & 2 & 0 \\ 5 & 9 & 7 & 2 & \\ 14 & 16 & 9 & & \\ 30 & 25 & & & \\55 & & & & \end{array}$

So we can see that a(0)= 0, $\Delta(0)= 1$ , $\Delta^2(0)= 3$ , $Delta^3(0)= 2$ and all succeeding differences are 0.
Now, Newton's divided difference formula becomes $a(0)+ \Delta(0)n+ \Delta^2(0)/2 n(n-1)+ \Delta^3(0)/3! n(n-1)(n-2)$ $= 0+ n+ (3/2)n(n-1)+ (2/6)n(n-1)(n-2)$ and all succeeding terms are 0. If we factor out a 1/6, that becomes

$\frac{1}{6}(6n+ 9n(n-1)+ 2n(n-1)(n-2))$ $= \frac{1}{6}(6n+ 9n^2- 9n+ 2n^3- 6n^2+ 4n$ $= \frac{1}{6}(2n^3+ 3n^2+ n)= \frac{1}{6}(n(2n+1)(n+1)$

exactly the formula you give.

Blast! Soroban beat me again!

**flyingsquirrel** · December 10th 2009, 05:41 AM

Originally Posted by xcluded

Hi , i'm not sure how my lecturer got this. may i know what he did in between to derive this ?

$1^2 + 2^2 + .... + n^2$

$= (\frac{n}{6})(n+1)(2n+1)$

Here is another way to derive this formula (I read it in the book titled Concrete Mathematics):

Let $S_n=\sum_{k=1}^nk^2 = 1+(2\times 2)+(3\times 3)+\cdots +(n\times n)$ .

$\begin{aligned} S_n = & \phantom{+\,\,\,}{\color{blue}1} \\ & +{\color{blue} 2} + {\color{red}2}\\ & + {\color{blue}3} + {\color{red}3} + 3\\ & + \ldots\\ & + \underbrace{{\color{blue}k}+{\color{red}k}+k+\cdot s +k}_{k\text{ terms}} \\ & + \ldots \\ & + \underbrace{{\color{blue}n} + {\color{red}n} + n +\cdots +n}_{n\text{ terms}} \end{aligned} $

Summing the numbers of the same color gives

$ S_n = \left({\color{blue}\sum_{k=1}^nk}\right)+\left({\c olor{red}\sum_{k=2}^nk}\right) + \left(\sum_{k=3}^nk\right) + \cdots+\left(\sum_{k=n}^nk\right)= \sum_{j=1}^n\sum_{k=j}^nk $

As $\sum_{k=j}^n k = \frac{n+j}{2}\cdot (n-j+1)=\frac{1}{2} (n(n+1)+j-j^2)$ we have

$\begin{aligned} S_n&=\frac{1}{2}\sum_{j=1}^nn(n+1)+j-j^2\\ S_n&=\frac{n^2(n+1)}{2}+\left(\frac{1}{2}\sum_{j=1 }^nj\right)-\frac{1}{2}\sum_{j=1}^nj^2\\ S_n&=\frac{n^2(n+1)}{2}+\frac{1}{2}\cdot \frac{n}{2}(n+1)-\frac{1}{2}S_n\\ S_n &= \frac{n(n+1)(2n+1)}{4}-\frac{1}{2}S_n \end{aligned} $