Results 1 to 5 of 5

Math Help - 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 ?

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

    = (\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
    South Africa
    Posts
    1,630
    Thanks
    6
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,690
    Thanks
    617
    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] \\<br />
f(2) = 5: & 8a + 4b + 2c + d &=& 5 & [2] \\<br />
f(3) = 14: & 27a + 9b + 3c + d &=& 14 & [3] \\<br />
f(4) = 30: & 64a + 16b + 4c + d &=& 30 & [4] \end{array}

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

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

    . . \begin{array}{ccccccc}<br />
\text{Subtract [9] - [8]} && 6a \:=\:2 & \Rightarrow &\boxed{ a \:=\:\tfrac{1}{3}}<br />
\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}

    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,423
    Thanks
    1331
    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!
    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 ?

    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}<br />
  S_n      = &   \phantom{+\,\,\,}{\color{blue}1} \\<br />
         & +{\color{blue} 2} + {\color{red}2}\\<br />
         & + {\color{blue}3} + {\color{red}3} + 3\\<br />
         & + \ldots\\<br />
        &   + \underbrace{{\color{blue}k}+{\color{red}k}+k+\cdot  s +k}_{k\text{ terms}} \\<br />
        &   + \ldots \\<br />
       &    + \underbrace{{\color{blue}n} + {\color{red}n} + n +\cdots +n}_{n\text{ terms}}<br />
\end{aligned}<br />
    Summing the numbers of the same color gives
    <br />
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<br />
    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}<br />
S_n&=\frac{1}{2}\sum_{j=1}^nn(n+1)+j-j^2\\<br />
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\\<br />
S_n&=\frac{n^2(n+1)}{2}+\frac{1}{2}\cdot \frac{n}{2}(n+1)-\frac{1}{2}S_n\\<br />
S_n &= \frac{n(n+1)(2n+1)}{4}-\frac{1}{2}S_n<br />
\end{aligned}<br />
    Finally solving for S_n gives us
    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: July 4th 2011, 05:58 AM
  2. Problem Involving Arithmetic progression
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: September 30th 2010, 08:33 AM
  3. Arithmetic progression problem
    Posted in the Pre-Calculus Forum
    Replies: 5
    Last Post: January 8th 2010, 10:23 PM
  4. Arithmetic Progression or Arithmetic Series Problem
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: October 8th 2009, 12:36 AM
  5. Arithmetic Progression Problem...
    Posted in the Algebra Forum
    Replies: 5
    Last Post: March 23rd 2009, 04:34 AM

Search Tags


/mathhelpforum @mathhelpforum