Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Another Sequence: Method

  1. Aug 28, 2004 #1
    Hello all

    I encountered the following problem in my textbook:

    Evaluate the sum: 1*2 + 2*3 + ... + n(n+1)

    The answer I know is: n(n+1)(n+2)/ 3. However I was wondering how they got that. Here is my solution:


    v(v+1)(v+2) (we are assuming that n is a rational function). Now I need to know what to subtract from

    v(v+1)(v+2). What do I do next? I know you have to subtract an expression, but what is that expression? After subtracting you have to sum from v = 0 to v = n. And we get the answer.

    Any help would be greatly appreciated, as it will help in many other problems of the same type.

    Thanks!
     
  2. jcsd
  3. Aug 28, 2004 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    I assume that "n is a rational function" MEANS "the solution is a rational function of n". I don't why you assume then that it must be of the form v(v+1)(v+2) (what is v?? The general index?) minus something.

    My first thought was "telescoping series". Looking at two consectutive terms, I not that (v-1)nv+ v(v+1)= v(v-1+v+1)= 2v2. In particular, if we assume that n is even, there exist an even number of terms and we have: 2(22+ 2(42)+... 2(n2). Since each "v" now is even, v= 2i for some i and (2i)2= 4i2 and we can factor both that 4 and the orignal 2 out to get 8 (12+ 22+... +(n/2)2) Remember that n is even here so n/2 is an integer. Do you know the formula for the sum of squares?

    If n is odd, then you can do the same for all terms up to n-1, then add n(n+1) to the sum.
     
  4. Aug 28, 2004 #3

    mathman

    User Avatar
    Science Advisor
    Gold Member

    There is a standard procedure called "mathematical induction" (which is NOT the same as induction in logic). The basic idea is to show that the formula is true for n=1, then assume it is true for n-1 and show it is true for n.

    Proof n=1: 1*2=1*2*3/3
    Assume 1*2+...+(n-1)*n=(n-1)*n*(n+1)/3
    Add n*(n+1) to right hand side and you will get:
    (n-1)*n*(n+1)/3+n*(n+1)=n*(n+1)*((n-1)/3+1)=n*(n+1)*(n+2)/3
    QED
     
  5. Aug 28, 2004 #4

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Yes, but his question was not "how do they prove that?", but "how did they get that?". In order to apply "proof by induction, you first have to know what the formula is. Proof by induction won't help you there.
     
  6. Aug 28, 2004 #5

    Tide

    User Avatar
    Science Advisor
    Homework Helper

    Here's how to do it:

    Suppose you write your sum with index j ranging from 1 to N. Then each term in the sum is j(j+1). Now observe that [tex](j+1)^3-j^3 = 3 \times {j(j+1)} + 1[/tex] so [tex]j(j+1) = \frac {1}{3} \times \left( {(j+1)^3-j^3 -1 \right)[/tex].

    Now sum over j from 1 to N. Notice the first two terms above have opposite signs so that when you sum over j ALL the terms CANCEL except the first and last. The final term on the right side sums to N.

    Therefore, [tex]SUM = \frac{1}{3} \left[ \left( N+1 \right)^3 - 1 - N\right] [/tex]and your result follows with a little bit of algebra and rearrangement.
     
    Last edited: Aug 28, 2004
  7. Aug 29, 2004 #6

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Now THAT'S nice!
     
  8. Aug 29, 2004 #7

    Tide

    User Avatar
    Science Advisor
    Homework Helper

    Gee, thanks!
     
  9. Aug 31, 2004 #8
    One quick question:

    Would I do the same thing for this problem:

    1 / (1*2 )+ 1/ (2*3 ) + ... 1 / [n(n+1)]

    From the index v, would I do this:

    Sum v = 1 to v = n 1/(v+1) - 1/v. Can someone help me with this? thanks
     
  10. Aug 31, 2004 #9

    Tide

    User Avatar
    Science Advisor
    Homework Helper

    Yes, exactly! Just note that

    [tex]\frac{1}{j(j+1)} = \frac{1}{j} - \frac{1}{j+1}[/tex]

    and perform the same steps you did in the previous example to find, in this case,

    [tex]SUM = \frac{N}{N+1}[/tex]
     
  11. Sep 1, 2004 #10
    Let S[n]=∑ from k=1 to n [k(k+1)] (1)

    As a general rule (without entering in details-requires a good deal of knowledge of linear sequences theory) if the general term of a series ( here a[k]=k(k+1);k=1 to n ) does form a linear sequence then also the sequence of the partial sums [of the series] is itself linear,though inhomogeneous,the closed form (only in 'n') of its general term (that is exactly the sum of the series under investigation) has a general form similar to that of the general term ( here n(n+1) ) + [a constant].

    In our case the sequence of the general term ( a[k]=k(k+1);k=1 to n ) is a[1]=2,a[2]=6,a[3]=12,a[4]=20,a[5]=30,a[6]=42,a[7]=56,a[8]=72,..... and is linear,it's recurrence formula being:

    a[k+3]-3a[k+2]+3a[k+1]-a[k]=0 or (rewritten in a more convenient form):

    a[n]-3a[n-1]+3a[n-2]-a[n-3]=0 (2) characteristic to a linear sequence

    The justification of (2) is fairly simple;we have:

    a[2]-a[1]=6-2=4
    a[3]-a[2]=12-6=6
    a[4]-a[3]=20-12=8

    (a[3]-a[2])-(a[2]-a[1])=6-4=2
    (a[4]-a[3])-(a[3]-a[2])=8-6=2

    {(a[4]-a[3])-(a[2]-a[1])}-{(a[3]-a[2])-(a[2]-a[1])}=0 (3)

    and finally

    a[4]-3a[3]+3a[2]-a[1]=0 (3)

    The same holds for every n ≥ 4;in the general case we have exactly (2).

    Therefore (easy to justify if one have some basic knowledge of discrete mathematics but I will skip this step here) the closed form for the general term a[n] is a polynomial of the third degree:

    a[n]=A'n3+B'n2+C'n+D' (4)

    (by replacing in 4 the known relations a[1]=2,a[2]=6,a[3]=12,a[4]=20 and solving the system for A',...,D' we regain the familiar n(n+1) form because A'=D'=0,B'=C'=1).

    Relation (4) indicates that we must seek the sum of our initial series S[n] in the form of a third degree polynomial (not a second degree polynomial,here a[n] reduce indeed to a second order polynomial n(n+1) but this is a particular case)+[another constant]:

    S[n]=An3+Bn2+Cn+D (5)

    (D is a sum of two constants,one comes from the form of a[n] the other resulting from resolving the linear recurrence equation S[n]-S[n-1]=0)

    We have also that:

    S[1]=1*2=2 (6)
    S[2]=1*2+2*3=8 (7)
    S[3]=20 (8)
    S[4]=40 (9)

    Introducing now (6) (7) (8) and (9) in (5) we obtain a system of equations from which A,B,C,D can be evaluated (easily,if you substract the equations in a right way of course :-) ).

    A+B+C+D=2
    8A+4B+2C+D=8
    27A+9B+3C+D=20
    64A+16B+4C+D=40

    Finally

    A=1/3
    B=1
    C=2/3
    D=0

    Thus the seeked sum S[n] is:

    S[n]=(1/3)n3+n2+(2/3)n (10)
     
    Last edited: Sep 1, 2004
  12. Sep 16, 2004 #11
    Hello all

    I know that 1/ j(j+1) = 1/ j - 1/ j+1

    To get the Sum = N / N+1 we have to sum from j = 1 to j = n. The problem is, I try to do this, and get the numerator but not the denominator. Here is my solution:


    1/ j - 1/ j+1 = (j+1) - j / j(j+1)

    (1+1) - 1 / 1(1+1) + (2+1) - 2/ 2(2+1) + ... + (n+1) - n / n(n+1)

    The numerator is 1 + 1 + 1 + ... + N. But what about the denominator? Is it N+1 because all of the coefficients cancel?

    Any help would be greatly appreciated!

    Thanks
     
  13. Sep 16, 2004 #12
    Any out there that could verify what i am doing?

    Thanks
     
  14. Sep 16, 2004 #13

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper
    2015 Award

    Since the series originally posed is simply the sum of the first n integers and the first n squares, Tide's beautiful solution is the old binomial theorem trick for deducing recursively the closed form expression for the sum of the first n kth powers, in the case k=2, found in a footnote on page 27 of Courant's calculus book. It was exactly this footnote that made me realize as a freshman in college that I had at last been given a good book. I.e. there was more in that footnote than in any entire book I had used in high school.

    Metachristi's point is also the useful remark that once you know the formula is cubic, you only need to compute 4 cases to solve for the coefficients. I taught both these methods in a recent "proofs" class for teachers and math majors. The kids greatly enmjoyed seeing where such formulas come from. Last week in calculus we also used the more easily derived fact that the sum of the first n kth powers has form n^(k+1)/[k+1] plus lower degree terms, to easily compute the integrals of all power functions x^k, directly as a limit of Riemann sums.
     
    Last edited: Sep 16, 2004
  15. Sep 17, 2004 #14
    Hello

    How did courant even get (v+1)^3 - v^3 on page 27 in that foot note? He never explains that. Mathwonk, could you please explain to me what the general method Courant used was? Also, why is it that here you praise Courant and in another thread you say you dont like him because you do not want to "kinky 1910 problems?"
     
  16. Sep 17, 2004 #15

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Really there are no more steps to perform from
    [tex]\frac{1}{j(j+1)} = \frac{1}{j} - \frac{1}{j+1}[/tex]
    other than to notice that this is a "telescoping sum" - all the intermediate terms cancel out leaving only the first and last term.

    In this case, SUM = 1 - 1/2 + 1/2 -1/3 + 1/3 - 1/4 + 1/4 - ... + 1/n - 1/(n+1) = 1 - 1/(n+1) = n/(n+1)
     
  17. Sep 17, 2004 #16
    Thank you so much Gokul! That has really enlightened me! I was so stupid not to realize that! Again thanks
     
  18. Sep 19, 2004 #17
    you are not stupid at all, at least to me :biggrin:
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Another Sequence: Method
  1. Puzzled by sequence (Replies: 9)

Loading...