1. Arithmetic progression problem

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

$\displaystyle 1^2 + 2^2 + .... + n^2$

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

thanks

2. Prove by induction.

For n = 1:

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

Now let n = k:

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

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

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

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

So:

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

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

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

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

3. Hello, xcluded!

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

$\displaystyle 1^2 + 2^2 + \hdots + n^2 \;=\;\frac{n(n+1)(2n+1)}{6}$
We have: .$\displaystyle f(n) \;=\;1^2+2^2+3^2 + \hdots + n^2$

The first few values: .$\displaystyle 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.

. . $\displaystyle \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: .$\displaystyle f(n) \:=\:an^3 + bn^2 + cn + d$

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

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

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

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

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

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

Substitute into [5]: .$\displaystyle 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]: .$\displaystyle \tfrac{1}{3} + \tfrac{1}{2} + \tfrac{1}{6} + d \:=\:1 \quad\Rightarrow\quad\boxed{ d \:=\:0}$

Hence: .$\displaystyle 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: .$\displaystyle f(n) \;=\;\frac{n(n+1)(2n+1)}{6}$

4. 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, $\displaystyle \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, $\displaystyle \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 $\displaystyle 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 $\displaystyle 1^2= 1$, when n= 2, it is $\displaystyle 1^2+ 2^2= 5$, when n= 3, it is $\displaystyle 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
$\displaystyle \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, $\displaystyle \Delta(0)= 1$, $\displaystyle \Delta^2(0)= 3$, $\displaystyle Delta^3(0)= 2$ and all succeeding differences are 0.
Now, Newton's divided difference formula becomes $\displaystyle a(0)+ \Delta(0)n+ \Delta^2(0)/2 n(n-1)+ \Delta^3(0)/3! n(n-1)(n-2)$$\displaystyle = 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 \displaystyle \frac{1}{6}(6n+ 9n(n-1)+ 2n(n-1)(n-2))$$\displaystyle = \frac{1}{6}(6n+ 9n^2- 9n+ 2n^3- 6n^2+ 4n$$\displaystyle = \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!

5. 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 ?

$\displaystyle 1^2 + 2^2 + .... + n^2$

$\displaystyle = (\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 $\displaystyle S_n=\sum_{k=1}^nk^2 = 1+(2\times 2)+(3\times 3)+\cdots +(n\times n)$.
\displaystyle \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
$\displaystyle 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 $\displaystyle \sum_{k=j}^n k = \frac{n+j}{2}\cdot (n-j+1)=\frac{1}{2} (n(n+1)+j-j^2)$ we have
\displaystyle \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}
Finally solving for $\displaystyle S_n$ gives us
$\displaystyle S_n = \frac{2}{3}\cdot \frac{n(n+1)(2n+1)}{4}=\frac{n(n+1)(2n+1)}{6},$
as expected.