Sum of n terms generalizations

sponsoredwalk

Hi I finally understand that in order to sum n terms you do the following;

Sn = 1 + 2 + 3 + ... + n
Sn = n + (n-1) + (n-2) + ... + 3 + 2 + 1

---

…
Sn + Sn = (n-1) + (n-1) + (n-1) + (n-1)......
2Sn = n(n - 1)
Sn = n/2(n-1)
________________________________

How do you do this for n² terms using the above method, or for that matter any equation really.

I only ask because it's important in mathematical induction and I literally got scared away from Spivak's Calculus over this topic in the 2nd chapter


Sn² = 1² + 2² + 3² + ... + (n - 2)² + (n - 1)² + n²
Sn² = n² + (n - 1)² + (n - 2)² + ... + 3² + 2² + 1²

---

…

Sn² + Sn² = (1² + n²) + [2² + (n - 1)²]+ [3² + (n - 2)²] + ... + [3² + (n - 2)²] + [2² + (n - 1)²] + (1² + n²)

2Sn² = 2(1² + n²) + 2[2² + (n - 1)²] + 2[3² + (n - 2)²] + ...

2Sn² = 2(1² + n²) + 2[4 + n² - 2n + 1] + 2[9 + n² - 4n + 4] + ...

2Sn² = 2(1² + n²) + 2[5 + n² - 2n] + 2[13 + n² - 4n] + ...

I don't know where to go from here and I'm trying to get that equation; n(n+1)(2n+1)/6 and I'm also getting the method down to do it for n³ and so that I can prove (n + 1) is part of each equation using mathematical induction.

Victor

Do you mean the sum of all the numbers from 1 to n?

Σn = 1 + 2 + 3 + ... + n

etc.?

Using Σ is a bit kinder.

sponsoredwalk

Yeah Σn²

[latex] \sum_{x=1}^{n} x^2 \ = \ 1^2 \ + \ \ \ \ 2^2 \ \ \ \ \ \ \ + \ \ \ \ \ \ \ 3^2 \ \ \ \ \ + \ ... \ + \ (n \ - \ 2)^2 \ + \ (n \ - \ 1)^2 \ + \ n^2 [/latex]

[latex] \sum_{x=1}^{n} x^2 \ = \ n^2 + \ (n \ - \ 1)^2 \ + \ (n \ - \ 2)^2 \ + \ ... \ + \ \ \ \ \ 3^2 \ \ \\ \ \ \ \ \ + \ \ \ \ \ \ \ 2^2 \ \ \ \ + \ \ \ 1^2 [/latex]

MathsManiac

The technique you mentioned at the start only works for arithmetic series (where there's a constant difference between one term and the next) so it won't work for the sum of the first n squares or cubes, etc.

If you know what the answer is, then you can prove the result using induction. For example, the sum of the first n squares is n(n+1)(2n+1)/6 and you can prove this by induction. It's done here:
http://pirate.shu.edu/~wachsmut/ira/infinity/answers/sm_sq_cb.html

If you don't know the answer, there's a general technique for getting the sum of the first n numbers raised to any power, assuming you already have a formula for the powers less than it. In the case of squares, it goes as follows:

Note that for any number r, you can expand (r+1)^3 as r^3+3r^2+3r+1. It follows that (r+1)^3 - r^3 = 3r^2+3r+1.

Next you sum both sides of the above equation from 1 to n. The left-hand side is a "telescoping sum". If you write it out with dots, you'll see there's a lot of cancellation and you just get (n+1)^3 - 1. The right hand side involves the sum you're looking for, and sums you already know, so you can manipulate this to get your result.

sponsoredwalk

[latex] \sum_{x=1}^{4} x^2 \ = \ 1^2 \ + \ 2^2 \ + \ 3^2 \ + \ 4^2 [/latex]

[latex] \sum_{x=1}^{4} x^2 \ = \ 4^2 \ + \ 3^2 \ + \ 2^2 \ + \ 1^2 [/latex]

[latex] 2 \sum_{x=1}^{4} x^2 \ = \ (1^2 \ + \ 4^2) \ + \ (3^2 \ + \ 2^2) \ + \ (2^2 \ + \ 3^2) \ + \ (4^2 \ + \ 1^2) [/latex]

[latex] 2 \sum_{x=1}^{4} x^2 \ = \ 2(1^2 \ + \ 4^2) \ + \ 2(3^2 \ + \ 2^2) [/latex]

[latex] 2 \sum_{x=1}^{4} x^2 \ = \ 2(17) \ + \ 2(13) [/latex]

[latex] 2 \sum_{x=1}^{4} x^2 \ = \ 34 \ + \ 26 [/latex]

[latex] 2 \sum_{x=1}^{4} x^2 \ = \ 60 [/latex]

[latex] \sum_{x=1}^{4} x^2 \ = \ 30 [/latex]

It seems to work fine for this pattern so I don't see why a general equation cannot be formulated as I've half laid out in my original post.

Also, it's great to prove the formula using indction once you have the eq. but how do you generate the equation in the first place using the method I've shown?

You'd think one would like to prove the sum of n² terms can come about from basic principles before you prove this basic principle for all numbers

MathsManiac

sponsoredwalk wrote: »

[latex] \sum_{x=1}^{4} x^2 \ = \ 1^2 \ + \ 2^2 \ + \ 3^2 \ + \ 4^2 [/latex]

[latex] \sum_{x=1}^{4} x^2 \ = \ 4^2 \ + \ 3^2 \ + \ 2^2 \ + \ 1^2 [/latex]

[latex] 2 \sum_{x=1}^{4} x^2 \ = \ (1^2 \ + \ 4^2) \ + \ (3^2 \ + \ 2^2) \ + \ (2^2 \ + \ 3^2) \ + \ (4^2 \ + \ 1^2) [/latex]

[latex] 2 \sum_{x=1}^{4} x^2 \ = \ 2(1^2 \ + \ 4^2) \ + \ 2(3^2 \ + \ 2^2) [/latex]

[latex] 2 \sum_{x=1}^{4} x^2 \ = \ 2(17) \ + \ 2(13) [/latex]

[latex] 2 \sum_{x=1}^{4} x^2 \ = \ 34 \ + \ 26 [/latex]

[latex] 2 \sum_{x=1}^{4} x^2 \ = \ 60 [/latex]

[latex] \sum_{x=1}^{4} x^2 \ = \ 30 [/latex]

It seems to work fine for this pattern so I don't see why a general equation cannot be formulated as I've half laid out in my original post.

But the point is that the technique hasn't got you anywhere. You still had to evaluate all the squares and add them up.

sponsoredwalk wrote: »

Also, it's great to prove the formula using induction once you have the eq. but how do you generate the equation in the first place using the method I've shown?

The technique I outlined for the squares is a general one. To get the formula for the sum of [latex] r^k [/latex], you expand [latex] r^{k \ + \ 1} - r^k [/latex], and this allows you to get the formula you require from the previously derived formulae.

I'm not sure that a generalised form of this formula exists for all powers. is that what you ultimately want?

Reading your first post again, it seems to me that maybe you don't need to do this at all.

Are you trying to prove that the sum of the first n numbers rasied to some fixed power k is always divisible by n+1? If so, that doesn't necessarily mean that you need to find a formula for that expression.

Edit: I presume you're not trying to prove that last thing I mentioned, since it's false!

sponsoredwalk

Yeah the sum definitely exists, it's n(n+1)(2n+1)/6.

n(n+1)(2n+1)/6 = (n² + n)(2n + 1)/6

(2n³ + 2n² + n² + n)/6 = (2n³ + 3n² + n)/6

Tom Apostol mentions and uses this idea when explaining integration in his Calculus book, it's used in Stewarts calculus when describing Riemannian Sums.

I'm just trying to go deeper and deeper into the rabbit hole, first learn the method for the sum of "n" terms, which I did like 2 days ago, then the sum for "n²" terms now and then n³ terms to just be 100% sure. Then generalize to the sum of n to the power n terms and then use mathematical induction to generalise every single thing here.

MathsManiac

I know the sum exists for the squares, as was clear from my earlier post. But are you actually interested in a formula that works not just for squares but for all powers.

You mentioned Spivak. The first ten such formulae are listed in problem 2-6, and the generalised formula is given in terms of bernoulli numbers, in problem 26-16. This gives a formula which is of closed form in n (but not p, the power).

sponsoredwalk

Okay, Spivak's method is extremely smart - if my understanding of it is correct. I see you put it up here too but I didn't understand what you were implying.

It seems as though the formula;

[latex] (k \ + \ 1)^3 \ - \ k^3 \ = \ 3k^2 \ + \ 3k \ + \ 1 [/latex]

we can sum this equation n times to end up with;

[latex] (n \ + \ 1)^3 \ - \ 1 \ = \ 3 [ 1^2 \ + 2^2 \ + \ ... \ + \ n^2] + 3 [ 1 \ + \ 2 \ + \ ... \ + \ n] \ + \ n [/latex]

& you algebraically solve for the n^2 term, which I assume gives the formula I'm trying to derive.

I see that this method is a way to generalize the whole thing which is great!

Problem 7 shows the sum as Apostol originally has it too!

However, I don't understand everything yet. The left hand side of the above sum - I do not understand why the -1 is there, it seems as thought the L.H.S. sum as Spivak has it should be very different.

[latex] 2^3 \ - \ 1^3 \ = \ 3 \cdot 1^2 \ + \ 3 \cdot 1 \ + \ 1 [/latex]
[latex] 3^3 \ - \ 2^3 \ = \ 3 \cdot 2^2 \ + \ 3 \cdot 2 \ + \ 1 [/latex]

---

[latex] (3^3 \ + \ 2^3) \ + \ (-2^3 \ - \ 1^3) \ = \ ( 3 \cdot 2^2 \ \ + \ 3 \cdot 1^2 ) \ + \ ( 3 \cdot 2 \ + \ 3 \cdot 1 ) \ + \ (1 \ + \ 1) [/latex]
[latex] 35 \ - \ 9 \ = \ 15 \ + \ 9 \ + \ 2 [/latex]
[latex] 26 \ = \ 26 [/latex]

I just don't agebraically see how the sum ends up as Spivak has it displayed when he sums all the way up to n.


Also, in relation to the original question, I am trying to end up with the formula n(n+1)(2n+1)/6 using the original method. There are many equivalent ways to find the sum of n terms so I think there should be many ways to find the sum of n² terms. This method in Spivak (which I now understand better thanks to your help) is more powerful but I think the other method will work in being generalized also.

Fremen

It's because

[latex] \sum_{k=1}^n \left( (k + 1)^3 - k^3 \right) = \sum_{k=1}^n (k + 1)^3 -\sum_{k=1}^n k^3 = (n+1)^3 - 1 [/latex]

Because everything cancels except the last term in the first sum and the first term in the last sum.
Clearly this works for whatever power you choose to raise k to.

sponsoredwalk

Well I didn't get it until I hammered throught the algebra of it, I've done the sum up to n=4


[latex] (n \ + \ 1)^3 \ - \ n^3 \ = \ 3n^2 \ + \ 3n \ + \ 1 \ [/latex]

---

[latex] (1 \ + \ 1)^3 \ - \ (1)^3 \ = \ 3(1)^2 \ + \ 3(1) \ + \ 1 \ [/latex]

[latex] (2 \ + \ 1)^3 \ - \ (2)^3 \ = \ 3(2)^2 \ + \ 3(2) \ + \ 1 \ [/latex]

[latex] (3 \ + \ 1)^3 \ - \ (3)^3 \ = \ 3(3)^2 \ + \ 3(3) \ + \ 1 \ [/latex]

[latex] (4\ + \ 1)^3 \ - \ (4)^3 \ = \ 3(4)^2 \ + \ 3(4) \ + \ 1 \ [/latex]
__________________________________________

[latex] [ 5^3 \ + \ 4^3 \ + \ 3^3 \ + \ 2^3 \ + \ 2^3 \ + \ 1^3 ] \ - \ [ + \ (4)^3 \ + \ (3)^3 \ + \ (2)^3 \ + \ (2)^3 \ + \ (1)^3 ] \ = \ [ 3(4)^2 \ + \ 3(3)^2 \ + \ 3(2)^2 \ + \ 2(1)^2 ] \ + \ [ 3(4) \ + \ 3(3) \ + \ 3(2) \ + \ 2(1) ] \ + \ 4 [/latex]

[latex] 5^3 \ = \ 3(4^2 \ + \ 3^2 \ + \ 2^2 \ + \ 1^2) \ + \ 3(4 \ + \ 3 \ + \ 2 \ + \ 1) \ + \ 4 [/latex]

[latex] 5^3 \ = \ 3(4^2 \ + \ 3^2 \ + \ 2^2 \ + \ 1^2) \ + \ 3(4 \ + \ 3 \ + \ 2 \ + \ 1) \ + \ 4 [/latex]

[latex] 5^3 \ = \ 3 \sum_{x=1}^{4} (x^2) \ + \ 3 \sum_{x=1}^{4} (x) \ + \ 4 [/latex]

[latex] 5^3 \ = \ 3 \sum_{x=1}^{4} (x^2) \ + \ 3 [ \frac{n(n \ + \ 1)}{2} ] \ + \ 4 [/latex]

[latex] 5^3 \ = \ 3 \sum_{x=1}^{4} (x^2) \ + \ 3 [ \frac{4(4 \ + \ 1)}{2} ] \ + \ 4 [/latex]

[latex] 5^3 \ = \ 3 \sum_{x=1}^{4} (x^2) \ + \ 30 \ + \ 4 [/latex]

[latex] (125) \ = \ 3 \sum_{x=1}^{4} (x^2) \ + \ 34 [/latex]

[latex] \frac{125 \ - \ 34}{3} \ = \ \sum_{x=1}^{4} (x^2)[/latex]

[latex] 30.33333... \ = \ \sum_{x=1}^{4} (x^2)[/latex]

So, as you see I'm 0.33333..... off

seandoiler

your sum on the left hand side is wrong...it should be 5^3 - 1^3 =124

Fremen

sponsoredwalk wrote: »

[latex] [ 5^3 \ + \ 4^3 \ + \ 3^3 \ + \ 2^3 \ + \ 2^3 \ + \ 1^3 ] \ - \ [ + \ (4)^3 \ + \ (3)^3 \ + \ (2)^3 \ + \ (2)^3 \ + \ (1)^3 ] \ = \ [ 3(4)^2 \ + \ 3(3)^2 \ + \ 3(2)^2 \ + \ 2(1)^2 ] \ + \ [ 3(4) \ + \ 3(3) \ + \ 3(2) \ + \ 2(1) ] \ + \ 4 [/latex]

This is more or less the problem. You're summing (n+1)^3 - n^3 from n=1 to n=4. That means there shouldn't be a 1^3 term in your first bracket, so you're off by one.
Eventually you divide by three, which is where the error of .333 comes from.

sponsoredwalk

Yeah a totally stupid mistake! It was 6am and I was pretty much just up

I actually remember looking back and changing it because I glanced up and thought "oh wait I messed up!". Psh.... :rolleyes:

Well, I'm so happy I've got this thing down! Thank you guys so much!

(n + 1)³ - n³ = n³ + 3n² + 3n + 1 - n³

Which, when we clean this up becomes;

(n + 1)³ - n³ = 3n² + 3n + 1

To get the answer.

(1 + 1)³ - 1³ = 3(1)² + 3(1) + 1
(2 + 1)³ - 2³ = 3(2)² + 3(2) + 1
(3 + 1)³ - 3³ = 3(3)² + 3(3) + 1
....
....
....
(n + 1)³ - n³ = 3n² + 3n + 1

---

(n + 1)³ - 1³ = 3∑(n²) + 3∑(n) + n

Using this we'll solve for ∑n².

(n + 1)³ - 1³ = 3∑(n²) + 3[n(n+1)/2] + n

n³ + 3n² + 3n + 1 - 1³ = 3∑(n²) + 3[n(n+1)/2] + n

n³ + 3n² + 3n - 3[n(n+1)/2] - n = 3∑(n²)

n³ + 3n² + 2n - 3[n(n+1)/2] = 3∑(n²)

n³ + 3n² + 2n - [3n²+3n/2] = 3∑(n²)

2n³ + 6n² + 4n - 3n² - 3n = 6∑(n²)

6∑(n²) = 2n³ + 6n² + 4n - 3n² - 3n

6∑(n²) = 2n³ + 3n² + n

∑(n²) = 1/3n³ + 1/2n² + 1/6n

∑(n²) = 1/3n³ + 1/2n² + 1/6n


:pac::pac::pac::pac::pac: