Results 1 to 9 of 9

Math Help - Formula for 1+(1+2)+(1+2+3)+(1+2+3+4)+...

  1. #1
    Senior Member OReilly's Avatar
    Joined
    Mar 2006
    Posts
    340

    Formula for 1+(1+2)+(1+2+3)+(1+2+3+4)+...

    Can someone show me the formula for calculating 1+(1+2)+(1+2+3)+(1+2+3+4)+...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by OReilly
    Can someone show me the formula for calculating 1+(1+2)+(1+2+3)+(1+2+3+4)+...
    Yes, I presume you have a finite sum.
    ---
    The key in the the fact that,
    1+2+...+x=\frac{x(x+1)}{2}
    ---
    Therefore, that entire sum is,
    \frac{1(2)}{2}+\frac{2(3)}{2}+...+\frac{n(n+1)}{2}
    Thus,
    \sum_{k=1}^{n}\frac{k(k+1)}{2}=\frac{1}{2}\sum_{k=  1}^n k^2+k
    Thus, subdivide the summation,
    \frac{1}{2}\sum_{k=1}^n k^2+\frac{1}{2}\sum_{k=1}^n k
    Use the fact above, and the sum of squares formula,

    \frac{1}{2}\cdot \frac{n(n+1)}{2}+\frac{1}{2}\cdot \frac{n(n+1)(2n+1)}{6}
    Simplify,
    \frac{n(n+1)}{4}+\frac{n(n+1)(2n+1)}{12}
    Add, common denominator and add,
    \frac{3n(n+1)+n(n+1)(2n+1)}{12}
    Thus, (factor),
    \frac{n(n+1)(3+2n+1)}{12}
    Simplify again,
    \frac{n(n+1)(2n+4)}{12}
    Simplify again,
    \frac{n(n+1)(n+2)}{6}
    ~~~
    Just for refernce, the sum of squares formula is,
    \sum_{k=1}^nk^2=\frac{n(n+1)(2n+1)}{6}
    ----
    I think it is cool that,
    \left( \begin{array}{c}n+2\\3 \end{array} \right)=\frac{(n+2)(n+1)n}{3!}

    That means you can calculate the sum by taking 2 more than number of terms and finding the number of combinations of forming three.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member OReilly's Avatar
    Joined
    Mar 2006
    Posts
    340
    Thanks!

    I didn't know sum of squares formula.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,914
    Thanks
    779
    Hello,OReilly!

    TPHacker is absolutely correct . . . Nice job, T.P. !

    If we are desperate, we could find the formula "from scratch".


    Can someone show me the formula for calculating:
    . . . 1+(1+2)+(1+2+3)+(1+2+3+4)+\hdots

    Crank out a list of the first few sums:

    \begin{array}{ccccccccc}S_1\:=\:1 \\ S_2\:=\:1 + 3\:=\:4\\S_3\:=\:1 + 3 + 6\:=\:10\\ S_4\:=\:1 + 3+6+10 \:=\:20\\ S_5\:=\:1+3+6+10+15\:=\:35 \\S_6\:=\:1+3+6+10+15+21\:=\:56\\ S_7\:=\:1+3+6+10+15+21+28 \;=\;84\\   \vdots\end{array}


    We have a function f(n). .For  n = 1,2,3,\hdots

    . . the function has consecutive values: . 1\quad4\quad10\quad20\quad56\quad84\;\hdots

    Take differences of consecutive terms: . . 3\quad6\quad\;10\;\quad15\quad21\;\hdots

    Take differences again: . . . . . . . . . . . . . . 3\quad\;4\quad\;\;5\quad\;\;6\;\hdots

    Take differences again: . . . . . . . . . . . . . . . 1\quad\;1\quad\;\:1\;\hdots


    We have a series of constants at the third differences.
    . . Hence, f(n) is a third-degree polynomial ... a cubic.

    Hence, the function is of the form: . f(n)\:=\:an^3 + bn^2 + cn + d
    . . and we must determine a,b,c,d.


    Use the first four values from our list.

    S_1\,=\,1:\;\;a\cdot1^3 + b\cdot1^2 + c\cdot1 + d\:= \:1\quad\;\;\;\Rightarrow\quad\;\; a+b+c+d\;=\;1
    S_2\,=\,4:\;\;a\cdot2^3 + b\cdot2^2 + c\cdot2 + d \:= \: 4\;\;\;\quad\Rightarrow\quad\; 8a + 4b +2c + d \;= \;4
    S_3\,=\,10:\;a\cdot3^3 + b\cdot3^2 + c\cdot3 + d \:=  \:10\quad\Rightarrow\quad 27a + 9b + 3c + d \;= \;10
    S_4\,=\,20:\;a\cdot4^3 + b\cdot4^2 + c\cdot4 + d\:= \:20\quad\Rightarrow\quad 64a + 16b + 4c + d \;= \;20


    Now we must solve this system of equations . . . but it's easy!

    . . \begin{array}{cccc}a+b+c+d\:=\:1 \\ 8a + 4b + 2c + d \:=\:4 \\ 27a + 9b + 3c + d \:= \:10\\ 64a + 16b + 4c + d \:=\:20\end{array}\;\begin{array}{cccc}(1)\\(2)\\(  3)\\(4)\end{array}

    Subtract (1) from (2): . 7a + 2b + c \:= \:3\quad\;\;\;(5)
    Subtract (2) from (3): . 19a + 5b + c \:= \:6\quad\;(6)
    Subtract (3) from (4): . 376a + 7b + c \:= \:10\;\;(7)

    Subtract (5) from (6): . 12a + 2b\:=\:3\;\;(8)
    Subtract (6) from (7): . 18a + 2b\:=\:4\;\;(9)

    Subtract (8) from (9): . 6a\,=\,1\quad\Rightarrow\quad \boxed{a = \frac{1}{6}}

    Substitute into (8): . 12\left(\frac{1}{6}\right) + 2b\:=\:3\quad\Rightarrow\quad \boxed{b = \frac{1}{2}}

    Substitute into (5): . 7\left(\frac{1}{6}\right) + 3\left(\frac{1}{2}\right) + c\:=\:3\quad\Rightarrow\quad \boxed{c = \frac{1}{3}}

    Substitute into (1): . \frac{1}{6} + \frac{1}{2} + \frac{1}{3} + d\:=\:1\quad\Rightarrow\quad \boxed{d = 0}


    Therefore: . f(n)\:=\:\frac{1}{6}n^3 + \frac{1}{2}n^2 + \frac{1}{3}n\quad\Rightarrow\quad \boxed{f(n)\;=\;\frac{n(n+1)(n+2)}{6}}

    ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

    This "scratch"method can be used
    . . when we suspect we have a polynomial function.
    It is long and tedious, but it works.

    Of course, it is more efficient to learn a few sums-of-powers formula:

    . . \sum_{k=1}^n k \;= \;\frac{n(n+1)}{2}

    . . \sum_{k=1}^n n^2\;=\;\frac{n(n+1)(2n+1)}{6}

    . . \sum_{k=1}^n k^3\;= \;\frac{n^2(n+1)^2}{4}


    Note that the third formula is the square of the first formula,
    . . making it easier to memorize.

    But what about the implications?
    . . This means: . (1 + 2 + 3 + 4 + 5)^2\:=\:1^3+2^3+3^3+4^3+5^3

    It looks like a bad joke or a terrible blunder, doesn't it?

    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by Soroban
    We have a series of constants at the third differences.
    . . Hence, f(n) is a third-degree polynomial ... a cubic.
    Tell me something, is this a famous method? This is the second time I seen it used on this forum. When I was younger I developed many theorems concerning differences of a sequence. One of them you just used. (A sequence is a polynomial of degree n if and only if it takes n steps to reach a constanct sequence).
    ---
    I have a elegant prove with this rule that,
    a^{(m)}_k=\sum_{k=1}^nk^m is always a polynomial sequence.

    Consider an infinite sequence,
    0^m,1^m+0^m,2^m+1^m+0^m,...
    Its diffrence sequence is,
    0^m,1^m,2^m,3^m,...
    A polynomial sequence of degree m therefore m subtractions are required. In total we used m+1 subtractions on our original sequence. Thus there exists a polynomial sequence of degree m+1. Furthermore, the first coefficient is \frac{1}{(m+1)!}. Based on the fact the constant sequence follows the factorial.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by ThePerfectHacker
    Tell me something, is this a famous method?
    Yes, I seem to recall that it is associated with Newton's name, but that
    be a manifestation of false memory syndrome, but it is in Acton's
    "Numerical Methods that Work", which I swear by

    RonL
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,914
    Thanks
    779
    Hello, TPHacker!

    Tell me something, is this a famous method?

    I'm sure it is . . .

    I ran across many years ago in some book. .Since then, I've seen more efficient methods,
    but I like that very primitive method. .(But I don't use it unless I am forced to.)


    In case anyone is interested . . .
    I was shown this method in graduate school . . . quite an eye-opener.

    To find, for example, \sum^n_{k=1} k^4, we are expected to know the three "preceding" formulas:
    . . \sum^n_{k=1} k \:=\:\frac{n(n+1)}{2}\qquad\sum^n_{k=1} k^2 \:=\:\frac{n(n+1)(2n+1)}{6}\qquad\sum^n_{k=1} k^3\:=\:\frac{n^2(n+1)^2}{4}


    Consider the next-higher power and form: . k^5 - (k-1)^5

    We have: / k^5 - (k-1)^5\:=\;5k^4 - 10k^3 + 10k^2 - 5k + 1

    Now let k \,= \,n,\,n\!-\!1,\,n\!-\!2,\,...\,,\,3,\,2,\,1 and "stack" the equations.

    . . . . n^5 - (n-1)^5\;=\quad\;\;5n^4\quad -\quad\;\; 10n^3\quad + . .  10n^2\quad\; -\quad\; 5n\quad\; + 1
    (n-1)^5-(n-2)^5 \;= \:5(n-1)^4 - 10(n-1)^3 + 10(n-1)^2 - 5(n-1) + 1
    (n-2)^5-(n-3)^5 \;= \:5(n-2)^4 - 10(n-2)^3 + 10(n-2)^2 - 5(n-2) + 1
    . . . . . . \vdots . . . . . . . . . . . \vdots . . . . . . . . \vdots . . . . . . . \vdots . . . . . . . \vdots . . . \vdots
    . . 3^5\quad -\quad 2^5 \qquad= \quad\;\;5(3^4)\;\;\; -\;\;\; 10(3^3) .  +\;\;\; 10(3^2)\quad -\quad 5(3)\quad + 1
    . . 2^5\quad -\quad 1^5\qquad = \quad\;\;5(2^4)\;\;\; -\;\;\; 10(2^3) .  +\;\;\; 10(2^2)\quad -\quad 5(2)\quad + 1
    . . 1^5\quad -\quad 0^5 \qquad = \quad\;\;5(1^4)\;\;\; -\;\;\; 10(1^3) .  + \;\;\;10(1^2)\quad -\quad 5(1)\quad + 1


    Add the stack (most of the left side cancels out):

    . . n^5\;=\;5\left(\sum k^4\right) - 10\left(\sum k^3\right) +  10\left(\sum k^2\right) - 5\left(\sum k\right) + \left(\sum 1\right)

    We have: . n^5 \;= \;5\left(\sum k^4\right)-10\cdot\frac{n^2(n+1)^2}{4} +  10\cdot\frac{n(n+1)(2n+1)}{6}  - 5\cdot\frac{n(n+1)}{2} + n


    Then, after an enormous amount of algebra, we get:

    . . . . \boxed{\sum^n_{k=1} k^4\;=\;\frac{n(n+1)(2n+1)(3n^2 + 3n - 1)}{30}}

    Quick! . . . Add that to your list!
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor Quick's Avatar
    Joined
    May 2006
    From
    New England
    Posts
    1,024
    Quote Originally Posted by Soroban
    Quick! . . . Add that to your list!
    for a second I thought you were talking to me.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    This problem with the generalized exponent sum, I think, is a very elegant problem. The method I used is solving a system of equations which is the most primitive and complicated method. I then tried to find the patterns for these numbers... and failed. Later I learned the problem was solved in the 18th Century using bernouilli numbers.
    ---
    However, I believe I found an elegant way how to solve that nasty system of equations. I have not yet worked it out but I believe it might work. My idea, is that the matrix that you get is also the solution of the polynomial of best fit which can be calculated with least squares.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: July 15th 2011, 02:30 PM
  2. Replies: 8
    Last Post: September 5th 2010, 01:11 PM
  3. Replies: 1
    Last Post: April 26th 2010, 08:16 PM
  4. Velocity formula from a position formula
    Posted in the Calculus Forum
    Replies: 1
    Last Post: October 5th 2009, 03:50 PM
  5. Replies: 8
    Last Post: March 3rd 2009, 12:14 PM

Search Tags


/mathhelpforum @mathhelpforum