Take the 2-minute tour ×
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.

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|improve this question
    
What do you want? $\sum_{N=1}^k N^2 =\text{?} $ –  draks ... Mar 13 at 6:39
    
yes, how to derive the closed form of that sum –  Tangleman Mar 13 at 6:41

3 Answers 3

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|improve this answer
    
+1 nice. related: math.stackexchange.com/q/710452/19341 –  draks ... Mar 13 at 7:07
    
@draks... that is my question. I did say I recently learnt this myself –  Sabyasachi Mar 13 at 7:10
    
no offense. why not linking it? –  draks ... Mar 13 at 7:11
    
@draks... fair enough. I will. –  Sabyasachi Mar 13 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 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|improve this answer
    
absolute magic :D –  Sabyasachi Mar 13 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|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 at 6:47
    
@Tangleman does combinatorics work for you? see my answer. –  Sabyasachi Mar 13 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 at 6:58
    
@Tangleman being good at math(and combinatorics) will help you in computational complexity analysis. –  Sabyasachi Mar 13 at 7:01

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.