Solving Summation Problems: The Method Behind Another Sequence

[courtrigrad]

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!

 

[HallsofIvy]

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)= 2v². In particular, if we assume that n is even, there exist an even number of terms and we have: 2(2²+ 2(4²)+... 2(n²). Since each "v" now is even, v= 2i for some i and (2i)²= 4i² and we can factor both that 4 and the orignal 2 out to get 8 (1²+ 2²+... +(n/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.

 

[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

 

[HallsofIvy]

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.

 

[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.

 

[HallsofIvy]

Now THAT'S nice!

 

[Tide]

Gee, thanks!

 

[courtrigrad]

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

 

[Tide]

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

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}$$

 

[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'n³+B'n²+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]=An³+Bn²+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)n³+n²+(2/3)n (10)

 

[courtrigrad]

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

 

[courtrigrad]

Any out there that could verify what i am doing?

Thanks

 

[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.

 

[courtrigrad]

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 don't like him because you do not want to "kinky 1910 problems?"

 

[Gokul43201]

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}$$

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)

 

[courtrigrad]

Thank you so much Gokul! That has really enlightened me! I was so stupid not to realize that! Again thanks

 

[kronecker]

you are not stupid at all, at least to me