Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Can anyone explain to me how you would derive this ? I have this question asked in a CS class and can't figure out how to derive it. it has to be derived as you would with sum of N

ex

1 2    3  ......  N 
N N-1  N-2    ....1 
---------------------
N+1 + N+1 + .... N+1 = N(N+1) SINCE THIS ADDITION IS 2 * THIS SUM THEN CLOSED FORM IS N(N+1)/ 2
share|cite|improve this question
    
What do you want? $\sum_{N=1}^k N^2 =\text{?} $ – draks ... Mar 13 '14 at 6:39
    
yes, how to derive the closed form of that sum – Tangleman Mar 13 '14 at 6:41

Okay, someone will post a method of common differences soon enough, so let's take a new approach. Combinatorics. Particularly because I recently learnt this myself.

Consider this: How many ways can I choose ordered triples $(a,b,c)$ from $0\le a,b\lt c\le n$?

For fixed $c$ this can be done in $c^2$ ways, because $a$ and $b$ can independently take values in the set $\{0,1,2,\cdots,c-1\}$. Since $c$ can take any value between $1$ and $n$, the total number of ways is $$1^2+2^2+\cdots+n^2$$

Now to find this number combinatorically!

There are $C(n+1,2)$ triples of the form $(a,a,c)$. To form triples of the form $(a,b,c)$ with $a\ne b$ We can select $a,b,c$ in $C(n+1,3)$ ways, and to each way there are two triples, $(a,b,c)$ and $(b,a,c)$.

Thus we can conclude that $$1^2+2^2+\cdots+n^2 = {n+1\choose 2}+2{n+1\choose 3}$$

share|cite|improve this answer
    
+1 nice. related: math.stackexchange.com/q/710452/19341 – draks ... Mar 13 '14 at 7:07
    
@draks... that is my question. I did say I recently learnt this myself – Sabyasachi Mar 13 '14 at 7:10
    
no offense. why not linking it? – draks ... Mar 13 '14 at 7:11
    
@draks... fair enough. I will. – Sabyasachi Mar 13 '14 at 7:12
    
@Sabyasachi you mentioned in the other link that you can derive this using method of common differences, do you know how to do it that way? – Tangleman Mar 13 '14 at 18:24

Here's my favourite trick for $\sum_{k=1}^N k^2$. Note that $(k+1)^3 - (k-1)^3 = 6 k^2 + 2$. So $$\sum_{k=1}^N \left((k+1)^3 - (k-1)^3\right) = \sum_{k=1}^N (6 k^2+2)$$ Now if you look closer at the sum on the left, you see a lot of cancellations: all the cubes from $2^3$ to $(N+1)^3$ are there with $+$ signs, and all those from $0^3$ to $(N-1)^3$ are there with $-$ signs. All that's left after cancellation is $N^3 + (N+1)^3 - 0^3 - 1^3 = N^3 + (N+1)^3 - 1$. On the right, we have $6 \sum_{k=1}^N k^2+ \sum_{k=1}^N 2 = 2 N + 6 \sum_{k=1}^N k^2$. Subtract $2N$ from both sides, divide by $6$ and simplify...

You can get a formula for $\sum_{k=1}^N k^3$ similarly, starting with $(k+1)^4 - (k-1)^4 = 8 k^3 + 8 k$.

share|cite|improve this answer
    
absolute magic :D – Sabyasachi Mar 13 '14 at 7:14

The result is a polynomial of third degree $ak^3+bk^2+cx+d$. Collect four examples $k=1,2,3,4$, get the coefficients $a,b,c,d$ and use proof by induction.

Good luck,

share|cite|improve this answer
    
I am really frustrated because the professor said he doesn't want to see induction! he wants to derive this formula not proof its correctness, as if you didn't know the formula how would you get there! he gave us example of sum of N but N^2 is a whole different monster – Tangleman Mar 13 '14 at 6:47
    
@Tangleman does combinatorics work for you? see my answer. – Sabyasachi Mar 13 '14 at 6:52
    
@Sabyasachi thanks, that does look like something he is asking but I don't quit understand the whole thing. I will try to study it more and see if I can get the jest of it. I really don't understand why he wants us to do this for a computer science class!! – Tangleman Mar 13 '14 at 6:58
    
@Tangleman being good at math(and combinatorics) will help you in computational complexity analysis. – Sabyasachi Mar 13 '14 at 7:01

This is similar to another answer, but I used consecutive terms in my derivation. I am taking these sums from 1 to N.

Once you know what the SUM(n) is, you can reduce SUM(n^2) to an algebraic expression containing the of SUM(n), where SUM(n) = N(N+1)/2. Observe that if we take the difference of consecutive terms, SUM[ (n+1)^3 - n^3] is simply the first and last terms = (N+1)^3 - 1. If we expand (n+1)^3 - n^3 we get 3n^2 + 3n + 1. So we can get an expression for SUM(n^2). 3SUM(n^2) + 3(SUM(n)) + SUM(1) = (N+1)^3 - 1. So 3SUM(n^2) + 3(N+1)N/2 + N = N^3 + 3N^2 + 3N. Just solve for SUM(n^2). SUM(n^2) = (2N^3 + 3N^2 + N)/6

You can expand SUM[(n+1)^4 - n^4] to get SUM(n^3) in a similar way once you know SUM(n^2) and SUM(n), and on and on to get any SUM of n raised to any power.

share|cite|improve this answer
    
Please use Latex formatting. All mathematical expressions should be in $ signs – Rise Dec 11 '15 at 14:49
    
Welcome to MSE. On this site we use MathJaX to format our maths. Here you can find a basic tutorial. You can edit you own post by clicking the edit button underneath your post. – gebruiker Dec 11 '15 at 14:49

By educated guess, the sum will be a polynomial of the third degree in $n$ (because the first order difference is a quadratic polynomial) such that

  • there is no constant coefficient (no term $\to0$);

  • the leading coefficient is $\frac13$, as for an antiderivative (or because $(n+1)^3-n^3=3n^2+$ lower degree terms);

  • the coefficient of the quadratic term is $\frac12$.

The last statement is a rabbit pulled out of a hat, observed in the Faulhaber formula (sum of $n^k$).

Then

$$S_n=\frac{n^3}3+\frac{n^2}2+an.$$

From

$$S_1=1=\frac13+\frac12+a,$$ we deduce $$a=\frac16.$$


You can avoid the rabbit by solving

$$S_n=\frac{n^3}3+an^2+bn$$for $S_1=1$ and $S_2=5$.

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.