Solving the Sum of 1+4+9+16+...+n^2 for n=x

[Mentallic]

This problem has intrigued me for some time now. I don't have much prerequisite knowledge on the topic.

Homework Statement

Find the sum of $1+4+9+16+...+n^2$ for n=x and thus, find the sum after 50 terms.

The Attempt at a Solution

Well, I have studied sums for the simple arithmetic and geometric progressions, but this one clearly doesn't follow those patterns. Please, for any helpers, don't just throw formulas at me, I would like this to be solved from scratch if need be (formulas being proven before being used). Thanks for any help.

 

[Count Iblis]

There is a simple trick and a more general approach.

Simple trick:

If you sum [(n+1)^3 - n^3 ] from n = 0 to N, the terms in the summation will cancel except the (n+1)^3 for n = N and the n^3 for n = 0, so the summation is (N+1)^3. But we also have that:

(n+1)^3 - n^3 = 3 n^2 + 3 n +1

So, it is also 3 times the desired summation plus 3 times the summation of the arithmetic series plus N.

 

[Mentallic]

Sorry I couldn't completely follow:

If you sum [(n+1)^3 - n^3 ] from n = 0 to N, the terms in the summation will cancel except the (n+1)^3 for n = N and the n^3 for n = 0

But skipping ahead for the moment:

So somehow (by your previous statement)
$$(n+1)^3-n^3=\sum_1^n{n^2}=3n^2+3n+1$$

and $n^2$ is just the last term in the series, or taking the n^th term in the sequence, then simply n²

and n is obviously the n^th term in the sequence.

Ok so testing for n=4,
$$\sum_1^4{n^2}=1+4+9+16=30$$

and $$3n^2+3n+1=3(4)^2+3(4)+1=61\neq 30$$

Well it's not working. I did something wrong

 

[hokie1]

You have some sign mistakes.

 

[Mentallic]

You have some sign mistakes.

Can you please point them out?

I'm checked my work, and the arithmetic seems correct.

The "formula" $3n^2+3n+1$ was never going to work anyway. I must be misunderstanding how to solve this.

 

[hokie1]

n³-(n-1)³ = n³-(n³-3n²+3n-1)=3n²-3n+1
On the left you go to
(n-1)³-(n-2)³
...
2³-1³

The sum of the left sides is n³-1

Now expand the right sides and sum those.
Solve for $$\sum n^{2}$$ on the right side and you have your formula

 

[Mentallic]

n³-(n-1)³ = n³-(n³-3n²+3n-1)=3n²-3n+1
On the left you go to
(n-1)³-(n-2)³

I'm going to need it re-explained as to why this is being done? How this is actually working. Sorry to be a hassle.

 

[hokie1]

No hassle at all. The idea is to sum from 1 to n or from 1² to n² in this case. So here I listed the sums in descending order. It could just have easily been written in ascending order:
2³-1³ = 7
3³-2³ = 19
...
(n-1)³-(n-2)³ = ...
n³-(n-1)³ = ...

The sum on the left is simple because almost all terms cancel out. The sum on the right is interesting in that the cube terms are removed leaving a sum of terms with exponents that are less than cubic. When the right side is regrouped and added we find so many squared terms, so many linear terms, and a constant.

Replace the $$\sum n$$ in the formula with the known formula for that expression. Now all you have left in the equation is a $$\sum n^{2}$$ term. Solve for that term to get the formula.

 

[hokie1]

My math professor referred to this as a technique. He said tricks are used once, techniques are used 2 or more times.

 

[Count Iblis]

I would call this a trick because the fact that we consider summing (n+1)^3 - n^3 is itself not derived using formal rules. We just do it because "it works".

 

[HallsofIvy]

You could use "Newton's divided difference method"
The sum you give has successive "partial sums" 1, 1+ 4= 5, 1+ 4+ 9= 14, 1+ 4+ 9+ 16= 30
Set the numbers up by
0 1 3 2
1 4 5 2
5 9 7
14 16
30


Where the first column is the list of partial sums. The second column are the succesive differences from the first column ,third column is the differences from the second column, and the fourth is the differences form the third column. We could continue, but obviously the second column is those squares and the third consecutive is successive odd numbers ($(n+1)^2- n^2= n^2+ 2n+ 1- n^2= 2n+1$) so the fourth column is all "2"s and all succeeding columns are "0"s.

Now "Newton's divided difference formula" says the the formula for f(n) giving the first column is $f(0)+ \Delta f(0) n+ \frac{\Deltaj^2 f(0)}{2}n(n-1)+ \cdot\cdot\cdot$. That's a lot like "McLaurin series" using the "differences" rather than derivatives and "factorial" powers rather than ordinary powers. Here this would be $0+ 1(n)+ (3/2!)n(n-1)+ (2/3!)n(n-1)(n-2)$.


We can factor an "n" out of that: $n(1+ (3/2)(n-1)+ (1/3)(n^2- 3n+ 2)= n\frac{6+ 9n- 9+ 2n^2- 6n+ 4}{6}$$= n\frac{1+ 3n+ 2n^2}{6}= \frac{n(n+1)(2n+1)}{6}$.

Notice, by the way, that "Newton's divided difference formula" implies that a sum of $n^{th}$ powers of n is an $n+1$ degree polynomial. Since here we are summing squares, the sum must be a cubic polynomial, of the form $an^3+ bn^2+ cn+ d$. When n= 1, $a+ b+ c+ d= 1$. When n= 2, $8a+ 4b+ 2c+ d= 5$. When n= 3, [itex]27a+ 9b+ 3c+ d= 14. When n= 4, $64a+ 16b+ 4c+ d= 30$. That gives four equations to solve for a, b, c, d and should give the same answer as above. In fact, notice that the first thing you can do is subtract two succesive equations to eliminate d, then subtract to eliminate, c, etc. You will basically reproduce the "difference table" above!

 

[hokie1]

Count Iblis the reason this is a technique and not a trick is that it allows a whole series of summation formulas to be created. The technique can be used to get the formula for sums of 1+2+ .. +n and anything else. This is not a trick exclusive to the sum of squares problem.

 

[Bohrok]

I've found these links very interesting with the sum of squares
http://answers.yahoo.com/question/i...UJ0NkeQjzKIX;_ylv=3?qid=20060822122232AAqlS8b
http://www.macalester.edu/~bressoud/pub/CBN2.pdf

 

[Count Iblis]

My favorite derivation is to use the formula:

$$\sum_{k=0}^{N}x^{k}=\frac{1-x^{N+1}}{1-x}$$

If we put x = exp(t), we get:

$$\sum_{k=0}^{N}\exp(kt)=\frac{1-\exp\left[(N+1)t\right]}{1-\exp(t)}$$

Then expand both sides in powers of t to see that the sum of powers are given by the Bernoulli polynomials.

 

[Mentallic]

Yes, now I remember. I used to be able to solve problems like this using the method that Hallsofivy showed. Completely slipped my mind about that method, and I never really understood why it worked, just that it was a handy tool to exploit.

My favorite derivation is to use the formula:

$$\sum_{k=0}^{N}x^{k}=\frac{1-x^{N+1}}{1-x}$$

If we put x = exp(t), we get:

$$\sum_{k=0}^{N}\exp(kt)=\frac{1-\exp\left[(N+1)t\right]}{1-\exp(t)}$$

Then expand both sides in powers of t to see that the sum of powers are given by the Bernoulli polynomials.

Oh uh... this maths is rightfully out of my league.

$$\sum_{k=0}^{N}x^{k}=\frac{1-x^{N+1}}{1-x}$$

This is following the same pattern as that with the cubic expansions just previously for x².

$$\frac{1-x^{N+1}}{1-x}=1-x+x^2-x^3...+(-x)^n$$

(if I got my expansion right that is)

No hassle at all. The idea is to sum from 1 to n or from 1² to n² in this case. So here I listed the sums in descending order. It could just have easily been written in ascending order:
2³-1³ = 7
3³-2³ = 19
...
(n-1)³-(n-2)³ = ...
n³-(n-1)³ = ...

The sum on the left is simple because almost all terms cancel out. The sum on the right is interesting in that the cube terms are removed leaving a sum of terms with exponents that are less than cubic. When the right side is regrouped and added we find so many squared terms, so many linear terms, and a constant.

Replace the $$\sum n$$ in the formula with the known formula for that expression. Now all you have left in the equation is a $$\sum n^{2}$$ term. Solve for that term to get the formula.

Thanks for that Yet, I still don't understand why the $n^3-(n-1)^3$ is valid?

 

[hokie1]

I'm not saying that the formula is valid I'm simply saying evaluate it. When you do you get an expression without a cubic term.