Results 1 to 5 of 5

Thread: Arithmetic progression problem

  1. #1
    Junior Member
    Joined
    Oct 2009
    Posts
    30

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Bar0n janvdl's Avatar
    Joined
    Apr 2007
    From
    Meh
    Posts
    1,630
    Thanks
    6
    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}$

    We already have:

    $\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$
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    12,028
    Thanks
    848
    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}$

    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Apr 2005
    Posts
    19,729
    Thanks
    3010
    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!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member flyingsquirrel's Avatar
    Joined
    Apr 2008
    Posts
    802
    Quote Originally Posted by xcluded View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Arithmetic progression problem.
    Posted in the Pre-Calculus Forum
    Replies: 5
    Last Post: Jul 4th 2011, 05:58 AM
  2. Problem Involving Arithmetic progression
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: Sep 30th 2010, 08:33 AM
  3. Arithmetic progression problem
    Posted in the Pre-Calculus Forum
    Replies: 5
    Last Post: Jan 8th 2010, 10:23 PM
  4. Arithmetic Progression or Arithmetic Series Problem
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: Oct 8th 2009, 12:36 AM
  5. Arithmetic Progression Problem...
    Posted in the Algebra Forum
    Replies: 5
    Last Post: Mar 23rd 2009, 04:34 AM

Search Tags


/mathhelpforum @mathhelpforum