# Another Sequence: Method

1. Aug 28, 2004

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. Aug 28, 2004

### HallsofIvy

Staff Emeritus
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.

3. Aug 28, 2004

### mathman

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

4. Aug 28, 2004

### HallsofIvy

Staff Emeritus
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.

5. Aug 28, 2004

### Tide

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 $$(j+1)^3-j^3 = 3 \times {j(j+1)} + 1$$ so $$j(j+1) = \frac {1}{3} \times \left( {(j+1)^3-j^3 -1 \right)$$.

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, $$SUM = \frac{1}{3} \left[ \left( N+1 \right)^3 - 1 - N\right]$$and your result follows with a little bit of algebra and rearrangement.

Last edited: Aug 28, 2004
6. Aug 29, 2004

### HallsofIvy

Staff Emeritus
Now THAT'S nice!

7. Aug 29, 2004

### Tide

Gee, thanks!

8. Aug 31, 2004

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

9. Aug 31, 2004

### Tide

Yes, exactly! Just note that

$$\frac{1}{j(j+1)} = \frac{1}{j} - \frac{1}{j+1}$$

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

$$SUM = \frac{N}{N+1}$$

10. Sep 1, 2004

### metacristi

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
11. Sep 16, 2004

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

12. Sep 16, 2004

Any out there that could verify what i am doing?

Thanks

13. Sep 16, 2004

### mathwonk

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
14. Sep 17, 2004

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?"

15. Sep 17, 2004

### Gokul43201

Staff Emeritus
Really there are no more steps to perform from
$$\frac{1}{j(j+1)} = \frac{1}{j} - \frac{1}{j+1}$$
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)

16. Sep 17, 2004