Sum of First $n$ Squares Equals $frac{n(n+1)(2n+1)}{6}$












109












$begingroup$


I am just starting into calculus and I have a question about the following statement I encountered while learning about definite integrals:



$$sum_{k=1}^n k^2 = frac{n(n+1)(2n+1)}{6}$$



I really have no idea why this statement is true. Can someone please explain why this is true and if possible show how to arrive at one given the other?










share|cite|improve this question











$endgroup$








  • 1




    $begingroup$
    proofwiki.org/wiki/Sum_of_Sequence_of_Squares
    $endgroup$
    – Martin Sleziak
    Jun 28 '11 at 3:16






  • 3




    $begingroup$
    possible duplicate of Evaluate $sum_{k=1}^n k^2$ and $sum_{k=1}^n k(k+1)$ combinatorially
    $endgroup$
    – Grigory M
    Jun 28 '11 at 6:39










  • $begingroup$
    ...and there is also math.stackexchange.com/questions/47509/…
    $endgroup$
    – Grigory M
    Jun 28 '11 at 6:40






  • 1




    $begingroup$
    OP does not show any attempt not to advance research and previous work. For questions so people give negative feedback but why now do not? There are also cases where the question is put on hold and now they do not. Can, please be more consistent?
    $endgroup$
    – Luis Felipe
    Oct 22 '15 at 15:46






  • 1




    $begingroup$
    @LuisFelipe Some relevant discussions on meta: Why close old questions with accepted answers using the “no context” reason? and Is it good practice to analyse past questions by today standards?.
    $endgroup$
    – Martin Sleziak
    Nov 10 '15 at 11:24
















109












$begingroup$


I am just starting into calculus and I have a question about the following statement I encountered while learning about definite integrals:



$$sum_{k=1}^n k^2 = frac{n(n+1)(2n+1)}{6}$$



I really have no idea why this statement is true. Can someone please explain why this is true and if possible show how to arrive at one given the other?










share|cite|improve this question











$endgroup$








  • 1




    $begingroup$
    proofwiki.org/wiki/Sum_of_Sequence_of_Squares
    $endgroup$
    – Martin Sleziak
    Jun 28 '11 at 3:16






  • 3




    $begingroup$
    possible duplicate of Evaluate $sum_{k=1}^n k^2$ and $sum_{k=1}^n k(k+1)$ combinatorially
    $endgroup$
    – Grigory M
    Jun 28 '11 at 6:39










  • $begingroup$
    ...and there is also math.stackexchange.com/questions/47509/…
    $endgroup$
    – Grigory M
    Jun 28 '11 at 6:40






  • 1




    $begingroup$
    OP does not show any attempt not to advance research and previous work. For questions so people give negative feedback but why now do not? There are also cases where the question is put on hold and now they do not. Can, please be more consistent?
    $endgroup$
    – Luis Felipe
    Oct 22 '15 at 15:46






  • 1




    $begingroup$
    @LuisFelipe Some relevant discussions on meta: Why close old questions with accepted answers using the “no context” reason? and Is it good practice to analyse past questions by today standards?.
    $endgroup$
    – Martin Sleziak
    Nov 10 '15 at 11:24














109












109








109


81



$begingroup$


I am just starting into calculus and I have a question about the following statement I encountered while learning about definite integrals:



$$sum_{k=1}^n k^2 = frac{n(n+1)(2n+1)}{6}$$



I really have no idea why this statement is true. Can someone please explain why this is true and if possible show how to arrive at one given the other?










share|cite|improve this question











$endgroup$




I am just starting into calculus and I have a question about the following statement I encountered while learning about definite integrals:



$$sum_{k=1}^n k^2 = frac{n(n+1)(2n+1)}{6}$$



I really have no idea why this statement is true. Can someone please explain why this is true and if possible show how to arrive at one given the other?







sequences-and-series discrete-mathematics summation






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Dec 3 '17 at 0:54









Austin Mohr

20.1k35098




20.1k35098










asked Jun 27 '11 at 23:05









Nathan OsmanNathan Osman

7622711




7622711








  • 1




    $begingroup$
    proofwiki.org/wiki/Sum_of_Sequence_of_Squares
    $endgroup$
    – Martin Sleziak
    Jun 28 '11 at 3:16






  • 3




    $begingroup$
    possible duplicate of Evaluate $sum_{k=1}^n k^2$ and $sum_{k=1}^n k(k+1)$ combinatorially
    $endgroup$
    – Grigory M
    Jun 28 '11 at 6:39










  • $begingroup$
    ...and there is also math.stackexchange.com/questions/47509/…
    $endgroup$
    – Grigory M
    Jun 28 '11 at 6:40






  • 1




    $begingroup$
    OP does not show any attempt not to advance research and previous work. For questions so people give negative feedback but why now do not? There are also cases where the question is put on hold and now they do not. Can, please be more consistent?
    $endgroup$
    – Luis Felipe
    Oct 22 '15 at 15:46






  • 1




    $begingroup$
    @LuisFelipe Some relevant discussions on meta: Why close old questions with accepted answers using the “no context” reason? and Is it good practice to analyse past questions by today standards?.
    $endgroup$
    – Martin Sleziak
    Nov 10 '15 at 11:24














  • 1




    $begingroup$
    proofwiki.org/wiki/Sum_of_Sequence_of_Squares
    $endgroup$
    – Martin Sleziak
    Jun 28 '11 at 3:16






  • 3




    $begingroup$
    possible duplicate of Evaluate $sum_{k=1}^n k^2$ and $sum_{k=1}^n k(k+1)$ combinatorially
    $endgroup$
    – Grigory M
    Jun 28 '11 at 6:39










  • $begingroup$
    ...and there is also math.stackexchange.com/questions/47509/…
    $endgroup$
    – Grigory M
    Jun 28 '11 at 6:40






  • 1




    $begingroup$
    OP does not show any attempt not to advance research and previous work. For questions so people give negative feedback but why now do not? There are also cases where the question is put on hold and now they do not. Can, please be more consistent?
    $endgroup$
    – Luis Felipe
    Oct 22 '15 at 15:46






  • 1




    $begingroup$
    @LuisFelipe Some relevant discussions on meta: Why close old questions with accepted answers using the “no context” reason? and Is it good practice to analyse past questions by today standards?.
    $endgroup$
    – Martin Sleziak
    Nov 10 '15 at 11:24








1




1




$begingroup$
proofwiki.org/wiki/Sum_of_Sequence_of_Squares
$endgroup$
– Martin Sleziak
Jun 28 '11 at 3:16




$begingroup$
proofwiki.org/wiki/Sum_of_Sequence_of_Squares
$endgroup$
– Martin Sleziak
Jun 28 '11 at 3:16




3




3




$begingroup$
possible duplicate of Evaluate $sum_{k=1}^n k^2$ and $sum_{k=1}^n k(k+1)$ combinatorially
$endgroup$
– Grigory M
Jun 28 '11 at 6:39




$begingroup$
possible duplicate of Evaluate $sum_{k=1}^n k^2$ and $sum_{k=1}^n k(k+1)$ combinatorially
$endgroup$
– Grigory M
Jun 28 '11 at 6:39












$begingroup$
...and there is also math.stackexchange.com/questions/47509/…
$endgroup$
– Grigory M
Jun 28 '11 at 6:40




$begingroup$
...and there is also math.stackexchange.com/questions/47509/…
$endgroup$
– Grigory M
Jun 28 '11 at 6:40




1




1




$begingroup$
OP does not show any attempt not to advance research and previous work. For questions so people give negative feedback but why now do not? There are also cases where the question is put on hold and now they do not. Can, please be more consistent?
$endgroup$
– Luis Felipe
Oct 22 '15 at 15:46




$begingroup$
OP does not show any attempt not to advance research and previous work. For questions so people give negative feedback but why now do not? There are also cases where the question is put on hold and now they do not. Can, please be more consistent?
$endgroup$
– Luis Felipe
Oct 22 '15 at 15:46




1




1




$begingroup$
@LuisFelipe Some relevant discussions on meta: Why close old questions with accepted answers using the “no context” reason? and Is it good practice to analyse past questions by today standards?.
$endgroup$
– Martin Sleziak
Nov 10 '15 at 11:24




$begingroup$
@LuisFelipe Some relevant discussions on meta: Why close old questions with accepted answers using the “no context” reason? and Is it good practice to analyse past questions by today standards?.
$endgroup$
– Martin Sleziak
Nov 10 '15 at 11:24










30 Answers
30






active

oldest

votes


















62












$begingroup$

You can easily prove it by induction.



One way to find the coefficients, assuming we already know that it's a degree $3$ polynomial, is to calculate the sum for $n=0,1,2,3$. This gives us four values of a degree $3$ polynomial, and so we can find it.



The better way to approach it, though, is through the identity
$$ sum_{t=0}^n binom{t}{k} = binom{n+1}{k+1}. $$
This identity is true since in order to choose a $(k+1)$-subset of $n+1$, you first choose an element $t+1$, and then a $k$-subset of $t$.



We therefore know that
$$ sum_{t=0}^n A + Bt + Cbinom{t}{2} = A(n+1) + Bbinom{n+1}{2} + Cbinom{n+1}{3}. $$
Now choosing $A=0,B=1,C=2$, we have
$$ A+Bt + Cbinom{t}{2} = t^2. $$
Therefore the sum is equal to
$$ binom{n+1}{2} + 2binom{n+1}{3}. $$






share|cite|improve this answer









$endgroup$













  • $begingroup$
    That's a good method: +1! Concerning the polynomial approach, I think it could be enhanced by noticing that if $p_k(n)=sum_{i=1}^n i^k$ then, extending what you wrote, $p_kinmathbb Q[n]$, $partial p_k=k+1$, and $n(n+1),Big|,p_k$ for every $k$. For $k=2$ this reduces to 2 the coefficients to be found making this approach equally worth, isn't it?
    $endgroup$
    – AndreasT
    Mar 30 '13 at 15:58










  • $begingroup$
    That's a great approach. Can you tell me what's the name of this identity : $sum_{t=0}^n binom{t}{k} = binom{n+1}{k+1}$. Is it the Pascal triangle?
    $endgroup$
    – hlapointe
    Oct 21 '15 at 14:37






  • 1




    $begingroup$
    @hlapointe It probably does have a name but I can't think of any! Do let me know if you find out.
    $endgroup$
    – Yuval Filmus
    Oct 21 '15 at 15:27






  • 5




    $begingroup$
    I learned this as the hockey stick identity.
    $endgroup$
    – Slade
    Jan 11 '16 at 9:09



















135












$begingroup$

Another way (by Euler, I think), from the geometric sum:



$$1 + x + x^2 + cdots + x^n = frac{x^{n+1}-1}{x-1}$$



Differentiate both sides and multiply by $x$:



$$x + 2 x^2 + 3 x^3 + cdots + n x^{n} = frac{n x^{n+2}-(n+1) x^{n+1} +x}{(x-1)^2}$$



Differentiating once more, we get on the LHS



$$1 + 2^2 x + 3^2 x^2 + cdots + n^2 x^{n-1}$$



which, evaluated at $x=1$ gives our sum $sum_{k=1}^n k^2$. What remains (straightforward, but tedious) is to compute the derivative on the RHS, and evaluate it at $x to 1$ (eg, with L'Hopital rule).



It should be evident that this procedure also can be applied (though it also turns more cumbersome) for sums of higher powers.





(Update) here's a concrete derivation, using binomial expansion of the RHS around $(x-1)$:



$$g(x)=frac{x^{n+1}-1}{x-1}=frac{left(left(x-1right)+1right)^{n+1}-1}{x-1}=\=(n+1)+{n+1 choose 2}(x-1)+{n+1 choose 3}(x-1)^2+Oleft((x-1)^3right)$$



Hence $$(g'(x) , x)'={n+1 choose 2}+{n+1 choose 3}2 x + O(x-1)$$
which evaluated at $x=1$ gives the desired answer.



Applying the same procedure for higher powers, we get, for example:
$$ sum_{k=1}^n k^3={n+1 choose 2}+{n+1 choose 3}6+{n+1 choose 4}6$$






share|cite|improve this answer











$endgroup$









  • 11




    $begingroup$
    I must admit I didn't know this one even though the problem is quite popular. +1
    $endgroup$
    – Patrick Da Silva
    Jul 10 '11 at 1:33






  • 3




    $begingroup$
    So slick I laughed reading this!
    $endgroup$
    – ttt
    Jul 10 '11 at 16:54






  • 9




    $begingroup$
    I waited in order to gain the commenting privilege just to say this : You made me fall in love with calculus again !!
    $endgroup$
    – BS.
    Jul 11 '11 at 2:10










  • $begingroup$
    @leonbloy Interesting! Will look at this tomorrow!
    $endgroup$
    – Pedro Tamaroff
    Mar 24 '12 at 6:48










  • $begingroup$
    Really nice! +1
    $endgroup$
    – AndreasT
    Mar 30 '13 at 15:47



















67












$begingroup$

I like this visual proof, due to Man-Keung Siu. It appeared in the March 1984 issue of Mathematics Magazine.



enter image description here



See also two more proofs (as well as this one) in Roger Nelson's Proofs Without Words: Exercises in Visual Thinking.






share|cite|improve this answer









$endgroup$









  • 1




    $begingroup$
    In a similar vein are most posts in this MO-thread. Incidentally, another Mike posted Man-Keung Siu's proof there.
    $endgroup$
    – t.b.
    Jun 28 '11 at 5:21










  • $begingroup$
    Beautiful extension of the classic Gauss sum proof - I love this one!
    $endgroup$
    – Steven Stadnicki
    Oct 28 '11 at 22:20



















40












$begingroup$

Yet another proof(!)



Notice that $(k+1)^3 - k^3 = 3k^2 + 3k + 1$ and hence



$$(n+1)^3 = sum_{k=0}^n left[ (k+1)^3 - k^3right] = 3sum_{k=0}^n k^2 + 3sum_{k=0}^n k + sum_{k=0}^n 1$$



which gives you



$$begin{align}
sum_{k=1}^n k^2
& = frac{1}{3}(n+1)^3 - frac{1}{2}n(n+1) - frac{1}{3}(n+1) \
& = frac{1}{6}(n+1) left[ 2(n+1)^2 - 3n - 2right] \
& = frac{1}{6}(n+1)(2n^2 +n) \
& = frac{1}{6}n(n+1)(2n+1)
end{align}$$






share|cite|improve this answer











$endgroup$









  • 4




    $begingroup$
    The appeal of this proof is that it's sort of the discrete counterpart to the integral: $int_0^n x^2 dx= n^3/3$
    $endgroup$
    – leonbloy
    Jan 14 '13 at 19:35



















18












$begingroup$

Proof (by induction)



Basis: Check it for n = 1 (it works out).



Induction: Assume the result is true for a given value of $n$. That is, assume
$$
sum_{k = 1}^n k^2 = frac{n(n+1)(2n+1)}{6}.
$$
Try to show that the result holds for $n+1$.
$$
begin{align*}
sum_{k = 1}^{n+1} k^2 &= (n+1)^2 + sum_{k=1}^n k^2\
&= (n+1)^2 + frac{n(n+1)(2n+1)}{6}\
&= frac{6(n+1)^2 + n(n+1)(2n+1)}{6}\
&= frac{(n+1)(n+1+1)(2(n+1)+1)}{6}.
end{align*}
$$






share|cite|improve this answer











$endgroup$





















    16












    $begingroup$

    To verify the identity, note $rm:sum_{k=1}^n: k^2 = f(n) iff f(n+1) - f(n) = (n+1)^2:$ and $rm: f(1) = 1:. $ But it's rote polynomial arithmetic to check that the RHS polynomial satisfies this recurrence.



    To discover the identity, notice that any polynomial solution of the above recurrence has degree at most $3$. Hence it's easy to find the polynomial solution by substituting a cubic polynomial with undetermined coefficients.



    Generally one can give a formula for sums of power using Bernoulli polynomials (motivated by discrete analogs of integrals of powers). The general theory becomes much clearer when one studies finite difference calculus and umbral calculus.






    share|cite|improve this answer











    $endgroup$





















      14












      $begingroup$

      I think it's useful to report here another proof that I have posted on Mathoverflow.



      Write down numbers in an equilateral triangle as follows:



          1
      2 2
      3 3 3
      4 4 4 4


      Now, clearly the sum of the numbers in the triangle is $Q_n:=1^2+2^2+dots+n^2$. On the other hand, if you superimpose three such triangles rotated by $120^circ$ each, like these ones



          1          4          4 
      2 2 3 4 4 3
      3 3 3 2 3 4 4 3 2
      4 4 4 4 1 2 3 4 4 3 2 1


      then the sum of the numbers in each position equals $2n+1$. Therefore, you can double-count $3Q_n=frac{n(n+1)}{2}(2n+1)$. $square$



      The proof is not mine and I do not claim otherwise. I first heard it from János Pataki. It is similar (but simpler) to the proof appearing on Wikipedia as I am writing this.



      How to prove formally that all positions sum to $2n+1$? Easy induction: moving down-left or down-right from the topmost number does not alter the sum, since one of the three summand increases and one decreases. This is a discrete analogue of the Euclidean geometry theorem "given a point $P$ in an equilateral triangle $ABC$, the sum of its three distances from the sides is constant" (proof: sum the areas of $APB,BPC,CPA$), which you can mention as well.






      share|cite|improve this answer











      $endgroup$













      • $begingroup$
        Nice, though I think the proof by Man-Keung Siu mentioned above is related.
        $endgroup$
        – ShreevatsaR
        Mar 19 '14 at 16:39



















      12












      $begingroup$

      Sums of polynomials can be done completely mechanically (no insight required, just turn the handle!) using the discrete calculus. Bill Dubuque mentions this in his answer, but I think it's nice to see a worked example.



      Represent $k^2$ in terms of falling powers (easy by inspection in this case, but you can use Stirling subset numbers to convert): $$ k^2 = k^{underline 2} + k^{underline 1}$$



      Sums of falling powers are easy, just like integration of ordinary powers, except for the treatment of limits: $$ sum_{k=1}^n k^{underline 2} + k^{underline 1} = bigg({1over 3}k^{underline 3} + {1over 2}k^{underline 2}bigg) bigg|^{n+1}_0$$



      And then convert back into ordinary powers (by expansion, or using signed Stirling cycle numbers): $$ {1over 3}((n+1)^3 - 3(n+1)^2 + 2(n+1)) + {1over 2}((n+1)^2 - (n+1))$$



      And then you can rearrange to get the answer you want.






      share|cite|improve this answer











      $endgroup$





















        12












        $begingroup$

        A probabilistic method that I learned from Jim Pitman's book Probability (exercise 3.3.10) is as follows. Let $X$ be uniformly distributed on the set ${ 1, 2, ldots, n }$. Then
        $$ E(X^3) = (1^3 + 2^3 + ldots + n^3)/n $$
        and
        $$ E((X+1)^3) = (2^3 + 3^3 + ldots +(n+1)^3)/n. $$
        Subtracting the first of these from the second we get
        $$ E((X+1)^3 - X^3) = ((n+1)^3 - 1)/n $$
        and we can simplify both sides a bit to get
        $$ E(3X^2 + 3X + 1) = n^2 + 3n + 3.$$
        By linearity of expectation we can expand the left-hand side to get
        $$ 3 E(X^2) + 3 E(X) + 1 = n^2 + 3n + 3. $$



        Now $E(X) = (1+2+ldots+n)/n = (n+1)/2$. Substituting this in and solving for $E(X^2)$ gives



        $$ E(X^2) = {(n+1)(2n+1) over 6} $$
        but of course $E(X^2) = (1^2+2^2+cdots +n^2)/n$.



        Similarly, we can derive for each $k$
        $$ sum_{j=0}^{k-1} {k choose j} E(X^j) = sum_{l=1}^k {k choose l} n^{l-1} $$
        and so if we know $E(X^0), ldots, E(X^{k-2})$ we can solve for $E(X^{k-1})$. So this method generalizes to higher moments as well.






        share|cite|improve this answer









        $endgroup$













        • $begingroup$
          never seen such a demonstration like this, thanks!!!
          $endgroup$
          – jonaprieto
          Apr 25 '12 at 6:11










        • $begingroup$
          I was rather surprised when I saw this for the first time as well.
          $endgroup$
          – Michael Lugo
          Apr 25 '12 at 16:32






        • 1




          $begingroup$
          Nice, needs more up votes.
          $endgroup$
          – k.stm
          May 28 '13 at 7:13



















        11












        $begingroup$

        This is a method that I learned from Polya's Mathematics and Plausible Reasoning: Let $s(n) = 1 + 2 + cdots + n$ and let $t(n) = 1^2 + 2^2 + cdots + n^2$. Make a small table as follows:



           n = 1 2  3  4  5
        t(n) = 1 5 14 30 55
        s(n) = 1 3 6 10 15


        Note the ratio $r(n) = t(n)/s(n)$ for sucessive values of $n$:



        R(1) = 1 = 3/3
        R(2) = 5/3
        R(3) = 14/6 = 7/3
        R(4) = 30/10 = 3 = 9/3
        R(5) = 55/15 = 11/3


        Based on the pattern it seems that $r(n) = (2n+1)/3$ (and in fact it is: just prove it by induction). It follows that $t(n) = r(n)s(n)$. Now use the fact that $s(n) = n(n+1)/2$.






        share|cite|improve this answer









        $endgroup$





















          9












          $begingroup$

          A natural approach for this kind of problems when you don't know the result is to proceed as follows :



          We may want to write the sum $sum_{k=1}^n k^2$ as a telescopic sum, so we will try to find a polynomial of degree 3 ( why ? ) $P$ so that $Pleft( k+1 right) - Pleft(kright)=k^2$. Let $Pleft( x right) = ax^3+bx^2+cx$ for all reals $x$, then our constraint becomes :



          $k^2= aleft( left(k+1right)^3 - k^3 right) + bleft( left(k+1right)^2 - k^2 right) + c$



          Which after expanding and rearranging becomes :



          $k^2 = 3ak^2 + left( 3a+2b right)k + a+b+c$



          But we know that two polynomials are equal iff their coefficients are equal too, so we just need to solve this system :



          $left{ begin{aligned}
          a &= frac{1}{3} \
          3a+2b &= 0 \
          a+b+c &= 0
          end{aligned} right.$



          Which gives us $left( a,b,c right) = left( frac{1}{3}, frac{-1}{2}, frac{1}{6} right)$



          And Voilà, we just found the coefficients of our polynomial ! Now we just have to evaluate our telescopic sum :



          $sum_{k=1}^n k^2 = sum_{k=1}^n Pleft( k+1 right) - Pleft(kright) = Pleft(n+1right)-underbrace{Pleft(1right)}_{=0}$



          $sum_{k=1}^n k^2 = frac{1}{3}left(n+1right)^3 - frac{1}{2}left(n+1right)^2+frac{1}{6}left(n+1right)$



          $sum_{k=1}^n k^2 = frac{1}{6}left(n+1right)left( 2 left(n+1right)^2 - 3 left(n+1 right) + 1 right)$



          $sum_{k=1}^n k^2 = frac{1}{6}left(n+1right)left( 2n^2+n right)$



          $sum_{k=1}^n k^2 = frac{1}{6}nleft(n+1right)left(2n+1right)$



          Which completes the proof :-)






          share|cite|improve this answer









          $endgroup$





















            8












            $begingroup$

            The standard method is induction and you should look it up as it is a popular second example (first is $sum n$)



            Another argument is use: $$24n^2 +2= (2n+1)^3-(2n-1)^3$$ and get a telescoping sum.



            i.e $$24sum_1^n k^2 +2n = sum_1^n (2k+1)^3-sum_1^n (2k-1)^3$$ $$24sum_1^n k^2 +2n = (2n+1)^3-1$$
            $$24sum_1^n k^2 =8 n^3+12 n^2+4 n$$ $$24sum_1^n k^2 =4 n (n+1) (2 n+1)$$ $$sum_1^n k^2 = frac{n (n+1) (2 n+1)}{6}$$






            share|cite|improve this answer











            $endgroup$









            • 1




              $begingroup$
              For a combinatorial argument see Sivaram's answer here
              $endgroup$
              – kuch nahi
              Jun 27 '11 at 23:23



















            8












            $begingroup$

            Proof 1. (Exercise 2.5.1 in Dias Agudo, Cândido da Silva, Matemáticas Gerais III). Let $S:=sum_{k=1}^{n}k^{2}$. Consider $(1+a)^{3}=1+3a+3a^{2}+a^{3}$ and sum
            $(1+a)^{3}$ for $a=1,2,ldots ,n$:



            $$begin{eqnarray*}
            (1+1)^{3} &=&1+3cdot 1+3cdot 1^{2}+1^{3} \
            (1+2)^{3} &=&1+3cdot 2+3cdot 2^{2}+2^{3} \
            (1+3)^{3} &=&1+3cdot 3+3cdot 3^{2}+3^{3} \
            &&cdots \
            (1+n)^{3} &=&1+3cdot n+3cdot n^{2}+n^{3}
            end{eqnarray*}$$



            The term $(1+1)^3$ on the LHs of the 1st sum cancels the term $2^3$ on the RHS of the 2nd, $(1+2)^3$, the $3^3$, $(1+3)^4$, the $4^3$, ..., and $(1+n-1)^3$ cancels $n^3$. Hence



            $$(1+n)^{3}=n+3left( 1+2+ldots +nright) +3S+1$$



            and



            $$S=frac{n(n+1)(2n+1)}{6},$$



            because $1+2+ldots +n=dfrac{nleft( n+1right) }{2}$.



            Proof 2. (Exercise 1.42 in Balakrishnan, Combinatorics, Schaum's Outline of Combinatorics). From



            $$binom{k}{1}+2binom{k}{2}=k+2frac{kleft( k-1right) }{2}=k^{2},$$



            we get



            $$begin{eqnarray*}
            S &:&=sum_{k=1}^{n}k^{2}=sum_{k=1}^{n}binom{k}{1}+2binom{k}{2}
            =sum_{k=1}^{n}binom{k}{1}+2sum_{k=1}^{n}binom{k}{2} \
            &=&binom{n+1}{2}+2binom{n+1}{3} \
            &=&frac{nleft( n+1right) left( 2n+1right) }{6}.
            end{eqnarray*}$$






            share|cite|improve this answer











            $endgroup$





















              7












              $begingroup$

              Here's one using the Pertubation Method I learnt in Concrete Mathematics:
              $$S_n = sum_{0leq jleq n}j^3$$.
              $$S_n+(n+1)^3=sum_{0leq jleq n+1}j^3$$
              $$S_n+(n+1)^3=0+sum_{1leq jleq n+1}j^3$$
              Replacing $j$ by $j+1$ gives us
              $$S_n+(n+1)^3=sum_{1leq j+1 leq n+1}(j+1)^3$$
              Rewriting $1leq j+1leq n+1$ as $0leq jleq n$ and expanding$(j+1)^3$
              $$S_n+(n+1)^3=sum_{0leq j leq n}(j^3+1+3j^2+3j)$$
              By Associative law
              $$S_n+(n+1)^3=sum_{0leq j leq n}j^3 +sum_{0leq jleq n}1 + 3sum_{0leq j leq n}j^2+3sum_{0leq jleq n}j$$
              $S_n =sum_{0leq jleq n}j^3$, so it gets canceled.
              Rewriting $sum_{0leq jleq n}1$ and $sum_{0leq jleq n}j$ as $(n+1)$ and $frac{n(n+1)}{2}$ respectively
              $$(n+1)^3=(n+1)+frac{3n(n+1)}{2}+3sum_{0leq jleq n}j^2$$
              $$3sum_{0leq jleq n}j^2=(n+1)^3-frac{3n(n+1)}{2} - (n+1)$$
              $$3sum_{0leq jleq n}j^2=(n+1)(n^2+1+2n-frac{3n}{2}-1)$$
              $$3sum_{0leq jleq n}j^2=frac{(n+1)(2n^2+n)}{2}$$
              $$sum_{0leq jleq n}j^2=frac{n(n+1)(2n+1)}{6}$$
              Using the same methods, one can get closed forms for even higher sums like $sum_{j=0}^{n}j^3$ by taking $S_n = sum_{0leq jleq n}j^4$ and using the binomial expansion for $(j+1)^4$






              share|cite|improve this answer











              $endgroup$













              • $begingroup$
                Same thing as Michael Lugo's answer, btw.
                $endgroup$
                – Bananach
                Mar 3 '16 at 17:26



















              6












              $begingroup$

              A combinatorial proof:



              Let $S={1,2,dots,(n+1)},nge 2$ and $T={(x,y,z)|x.y,zin S,x< z,y< z}$.By counting the number of members of $T$ in $2$ different ways I will prove the formula.



              $1$st way:



              We will at first Choose $z$ form the set $S$.When $z$ is $1$ then there are no choices for $x,y$ so the no. of elements of $T$ with $z=0$ is zero.When $z=2$ the number of choices for $x$ is $1$ and so is for $y$(precisely $x=y=1$).When $z=3$ then $xin {1,2}$ and $yin {1,2}$ so total no. of choices equals $2^2$.In a similar manner when $z=k,(1le kle (n+1))$,no. of choices for $x$ equals $(k-1)$ and no. of choices for $y$ is also $(k-1)$. So total no . of elements of T with $z=k$ is $(k-1)^2$.



              So we will get the total no. of elements of $T$ by summing $(k-1)^2$ up from $1 $ to $(n+1)$.Hence $$|T|=sum _{l=1}^{(n+1)}(l-1)^2=sum_{k=1}^{n}k^2$$



              $2$nd way:



              Among the elements of $T$ consisting of three numbers from the set $S$, there are elements in $x=y$ and elements in which $xne y$.



              We can count the no. of elements in which $x=y$ by choosing two distinct nos. from $S$ and assigning $z$ with the lagest no. and $x,y$ with the smallest number. We can choose two distinct numbers from $S$ in $displaystyle binom{n+1}{2}$ ways, so the total no. elements having $x=y$ is $displaystyle binom{n+1}{2}$.



              Now we have to count the number of elements in which $xne y$.This means that $x,y$ are dinstict and as they are less than $z$ this means that all the three are distinct. So we can count no. of such elements in $T$ in the following way.At first we will choose three elements from the set $S$ and assign the largest value to $z$ and assign the other two values to $x,y$. Now we can choose three numbers from the set $S$ in $displaystyle binom{n+1}{3}$.From each such three element we can get two elements of the set $T$(Assigning the largest to $z$ and then assigning any one of then to $x$ and the other to $y$). So no. of elements of $T$ having $xne y$ is $2displaystyle binom{n+1}{3}$



              So by this method we have $|T|=displaystyle binom{n+1}{2}+2displaystyle binom{n+1}{3}$



              On equating the result obtained from both the methods we have
              $$sum_{k=1}^{n}k^2=displaystyle binom{n+1}{2}+2displaystyle binom{n+1}{3}=frac{n(n+1)(2n+1)}{6}$$



              Note that this can easily be extended to find the sum of $p$th power of integers.($pin mathbb{N})$






              share|cite|improve this answer









              $endgroup$





















                5












                $begingroup$

                Another simple proof could be as follows: note that each square
                can be written as a sum of odd numbers:



                $sum_{k=1}^n(2k-1)=n^2$.



                (that can be easily shown)



                When writing each square as a sum of odd numbers we get that



                $S=sum_{k=1}^n k^2=1 + (1+3) + (1+3+5) + ... =sum_{k=1}^n(n-k+1)(2k-1)=$



                $=(2n+3)sum_{k=1}^n k -(n+1)sum_{k=1}^n 1 -2S$.



                Therefore



                $3S=frac{(2n+3)n(n+1)}{2}-n(n+1)=frac{(2n+1)n(n+1)}{2}$.






                share|cite|improve this answer









                $endgroup$





















                  4












                  $begingroup$

                  $begin{aligned} & hspace{0.5in} begin{aligned}displaystyle sum_{1 le k le n}k^2 & = sum_{1 le k le n}~sum_{1 le r le k}r =sum_{1 le r le n}~sum_{r le k le n}r \& = sum_{1 le r le n}~sum_{1 le k le n}r-sum_{1 le r le n}~sum_{1 le k le r-1}r \& = nsum_{1 le r le n}r-frac{1}{2}sum_{1 le r le n}r(r-1) \& =frac{1}{2}n^2(n+1)-frac{1}{2}sum_{1 le r le n}r^2+frac{1}{2}sum_{1 le r le n}r \& =frac{1}{2}n^2(n+1)-frac{1}{2}sum_{1 le k le n}k^2+frac{1}{4}n(n+1) end{aligned} \& begin{aligned}impliesfrac{3}{2}sum_{1 le k le n}k^2 & = frac{1}{2}n^2(n+1)+frac{1}{4}n(n+1) \& = frac{1}{4}n(n+1)(2n+1) end{aligned}\& implies hspace{0.15in} displaystyle sum_{1 le k le n}k^2 = frac{1}{6}n(n+1)(2n+1).end{aligned}$






                  share|cite|improve this answer









                  $endgroup$













                  • $begingroup$
                    This is an approach that I like. It can be generalized to $$begin{align}f(n, m) &= sum_{k = 1}^n k^m \&= sum_{k = 1}^n sum_{r = 1}^k k^{m-1} \&= sum_{1 le r le k le n} k^{m-1} \&= sum_{r = 1}^n sum_{k=r}^n k^{m-1} \&= sum_{r=1}^n f(n, m-1 ) - f(r - 1 , m - 1) end{align}$$ to be able to recursively solve any case.
                    $endgroup$
                    – DanielV
                    Jan 11 '16 at 13:50



















                  3












                  $begingroup$

                  Yet another take. Start with the definition of falling factorial powers:



                  $begin{align}
                  x^{underline{r}}
                  = x (x - 1) dotsm (x - r + 1)
                  end{align}$



                  so that:



                  $begin{align}
                  Delta n^{underline{r}}
                  &= (n + 1)^{underline{r}} - n^{underline{r}} \
                  &= r n^{underline{r - 1}} \
                  sum_{0 le k < n} k^{underline{r}}
                  &= frac{n^{underline{r + 1}}}{r + 1}
                  end{align}$



                  (the last one is also easy to prove by induction, or otherwise).





                  Now note that:



                  $begin{align}
                  n^2
                  = n^{underline{2}} + n^{underline{1}}
                  end{align}$



                  so we can write:



                  $begin{align}
                  sum_{0 le k le n} k^2
                  &= sum_{0 le k < n + 1}
                  left( k^{underline{2}} + k^{underline{1}} right) \
                  &= frac{(n + 1)^{underline{3}}}{3}
                  + frac{(n + 1)^{underline{2}}}{2} \
                  &= frac{(n + 1) n (n - 1)}{3} + frac{(n + 1) n}{2} \
                  &= frac{(2 n + 1) (n + 1) n}{6}
                  end{align}$






                  share|cite|improve this answer









                  $endgroup$





















                    3












                    $begingroup$

                    My contribution:
                    $$begin{align}
                    sum_{k=1}^n k^2&=frac 14sum_{k=1}^n(2k)^2\
                    &=frac 14sum_{k=1}^nbinom {2k}2+binom {2k+1}2\
                    &=frac 14sum_{k=2}^{2n+1} binom k2\
                    &=frac 14binom {2n+2}3\
                    &=frac 14cdot frac {(2n+2)(2n+1)(2n)}{1cdot 2cdot 3}
                    =color{lightgrey}{frac{(n+1)(2n+1)n}{1cdot 2cdot 3}}\
                    &=frac 16n(n+1)(2n+1)quadblacksquare
                    end{align}$$






                    share|cite|improve this answer











                    $endgroup$













                    • $begingroup$
                      Why $sum_{k=1}^n (2k)^2=sum_{k=1}^nleft(binom{2k}{2}+binom{2k+1}{2}right)$?
                      $endgroup$
                      – user236182
                      Oct 21 '15 at 17:19






                    • 1




                      $begingroup$
                      @user236182 - For any integer $a$, $$a^2=frac {a(a-1)}2+frac {(a+1)a}2=binom a2+binom {a+1}2$$ Putting $a=2k$ gives the result used above.
                      $endgroup$
                      – hypergeometric
                      Oct 21 '15 at 23:04












                    • $begingroup$
                      Why $sum_{k=1}^{2n+1}binom{k}{2}=binom{2n+2}{3}$?
                      $endgroup$
                      – user236182
                      Oct 21 '15 at 23:07










                    • $begingroup$
                      @user236182 - The following is a well-known identity: $$sum_{k=m}^Nbinom km=binom {N+1}{m+1}$$ A proof of it may be found here as a solution to a recent question. Putting $N=2n+1$ results in the identity used in the solution.
                      $endgroup$
                      – hypergeometric
                      Oct 22 '15 at 14:42





















                    2












                    $begingroup$

                    Another way to prove this by induction goes as follows:



                    Base case: If $n=0$, then we have $0$ on the left hand side, and $0(0+1)(2(0)+1)/6=0$ on the right.



                    Induction step:



                    Consider the differences $L(j+1)-L(j)$, and $R(j+1)-R(j)$ where $L(j)$ indicates that we have $j$ for $n$ on the left hand side. Well, $L(j+1)-L(j)=(j+1)^2$, and
                    $$R(j+1)-R(j)=frac{(j+1)((j+1)+1))(2(j+1)+1)}{6} - frac{j(j+1)(2j+1)}{6}$$ which simplifies to $(j+1)^2$ also. So, the rates of change on both sides equal each other, and thus the induction step follows.






                    share|cite|improve this answer











                    $endgroup$





















                      2












                      $begingroup$

                      Another take, similar to Euler's (?) proof given by @leonbloy. We know that if:



                      $begin{align}
                      A(z)
                      &= sum_{n ge 0} a_n z^n
                      end{align}$



                      then (writing $mathtt{D}$ for the derivative):



                      $begin{align}
                      z mathtt{D} A(z)
                      &= sum_{n ge 0} n a_n z^n
                      end{align}$



                      Also:



                      $begin{align}
                      frac{A(z)}{1 - z}
                      &= sum_{n ge 0} left( sum_{0 le k le n} a_n right) z^n \
                      frac{1}{1 - z}
                      &= sum_{n ge 0} z^n
                      end{align}$



                      This you can repeat and combine. In our case, we get that:



                      $begin{align}
                      sum_{n ge 0} n^2
                      &= (z mathtt{D})^2 frac{1}{1 - z} \
                      &= frac{z + z^2}{(1 - z)^3} \
                      sum_{n ge 0} left( sum_{0 le k le n} k^2 right) z^n
                      &= frac{z + z^2}{(1 - z)^4}
                      end{align}$



                      We are interested in the coefficient of $z^n$:



                      $begin{align}
                      [z^n] frac{z + z^2}{(1 - z)^4}
                      &= [z^n] frac{z}{(1 - z)^4} + [z^n] frac{z^2}{(1 - z)^4} \
                      &= [z^{n - 1}] (1 - z)^{-4} + [z^{n - 2}] (1 - z)^{-4} \
                      &= (-1)^{n - 1} binom{-4}{n - 1} + (-1)^{n - 2} binom{-4}{n - 2} \
                      &= binom{n - 1 + 4 - 1}{4 - 1} + binom{n - 2 + 4 - 1}{4 - 1} \
                      &= binom{n + 2}{3} + binom{n + 1}{3} \
                      &= frac{(n + 2) (n + 1) n}{3!} + frac{(n + 1) n (n - 1)}{3!} \
                      &= frac{(2 n + 1) (n + 1) n}{6}
                      end{align}$



                      This approach is less messy than the cited one (no horrible derivatives and then l'Hôpital thrice).






                      share|cite|improve this answer











                      $endgroup$









                      • 1




                        $begingroup$
                        Its a bit awfully sophisticated for this fact but nice ^^
                        $endgroup$
                        – Hexacoordinate-C
                        Oct 21 '15 at 16:56



















                      2












                      $begingroup$

                      Another method:



                      $$begin{align}
                      sum_{k=1}^nk^2&=frac 12sum_{k=1}^n k(k+1)+(k-1)k\
                      &=frac 12 left[sum_{k=1}^n k(k+1)+sum_{k=1}^{n-1}k(k+1)right]\
                      &=color{lightgrey}{frac 12} left[ color{lightgrey}2sum_{k=1}^n binom {k+1}2+color{lightgrey}2sum_{k=1}^{n-1}binom {k+1}2right]\
                      &=binom {n+2}3+binom {n+1}3\
                      &=frac{color{blue}{(n+2)}(n+1)n}6+frac{(n+1)ncolor{blue}{(n-1)}}6\
                      &=frac {n(n+1)color{blue}{(2n+1)}}6quadblacksquare
                      end{align}$$






                      share|cite|improve this answer









                      $endgroup$





















                        2












                        $begingroup$

                        Here, we present an approach that uses only the sum of the arithmetic progression $sum_{k=1}^nk=frac12n(n+1)$.



                        Here, we note that $sum_{j=1}^k(1)=k$. Then, we can write



                        $$begin{align}
                        sum_{k=1}^nk^2&=sum_{k=1}^nksum_{j=1}^k(1)\\
                        &=sum_{j=1}^nsum_{k=j}^n,k\\
                        &=frac12sum_{j=1}^n(n+1-j)(j+n)\\
                        &=frac12sum_{j=1}^nleft(n(n+1)+j-j^2right)\\
                        &=frac12n^2(n+1)+frac14n(n+1)-frac12sum_{j=1}^nj^2\\
                        frac32sum_{k=1}^nk^2&=frac{(2n+1)n(n+1)}{4}\\
                        sum_{k=1}^nk^2&=frac{(2n+1)n(n+1)}{6}
                        end{align}$$






                        share|cite|improve this answer









                        $endgroup$





















                          2












                          $begingroup$

                          A High School Proof:
                          $$S_n = 1^2 + 2^2 + 3^2 +dots+ n^2$$



                          We know,



                          $$r^3 - 3r^2 + 3r - 1 = (r-1)^3 $$



                          $$r^3 - (r-1)^3 = 3r^2 - 3r + 1$$



                          When $r=1, 2, 3,dots, n$



                          $$1^3 - 0^3 = 3*1^2 - 3*1 + 1qquad(1)$$



                          $$2^3 - 1^3 = 3*2^2 - 3*2 + 1qquad(2)$$



                          $$3^3 - 2^3 = 3*3^2 - 3*3 + 1qquad(3)$$



                          $$dotsdotsdotsdotsdotsdotsdotsdotsdots$$



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



                          By summing all the equations (from 1 to n) we get,



                          $$n^3 - 0^3 = 3(1^2 + 2^2 + 3^2 +dots+ n^2) - 3(1+2+3+dots+n) + (1+1+1+dots)$$



                          $$n^3 = 3S_n - 3frac{n(n+1)}{2} + n$$



                          begin{align}
                          3S_n & = n^3 + frac{3n(n+1)}{2} - n\
                          & = frac{2n^3 + 3n^2 + 3n - 2n}{2}\
                          & = frac{2n^3 + 3n^2 + n}{2}\
                          & = frac{n(2n^2 + 3n + 1)}{2}\
                          & = frac{n(2n^2 + 2n + n + 1)}{2}\
                          & = frac{n{2n(n+1)+1(n+1)}}{2}\
                          & = frac{n(n+1)(2n+1)}{2}\
                          end{align}



                          $$therefore S_n = frac{n(n+1)(2n+1)}{6}$$






                          share|cite|improve this answer









                          $endgroup$





















                            0












                            $begingroup$

                            For proof by induction; these are the $color{green}{mathrm{three}}$ steps to carry out:



                            Step 1: Basis Case: For $i=1$: $$sum^{i=k}_{i=1} i^2=frac{1(1+1)(2times 1+1)}{6}= frac{2times 3}{6}=1$$ So statement holds for $i=1$.



                            Step 2: Inductive Assumption: Assume statement is true for $i=k$:



                            $$sum^{i=k}_{i=1} i^2=frac{k(k+1)(2k+1)}{6} $$



                            Step 3: Prove Statement holds for $i=k+1$. You need to prove that for $i=k+1$: $$sum^{i=k+1}_{i=1} i^2=color{blue}{frac{(k+1)(k+2)(2k+3)}{6}}$$



                            To do this you cannot use: $$sum^{i=k}_{i=n} i^2=color{red}{frac{n(n+1)(2n+1)}{6}} $$ as this is what you are trying to prove.



                            So what you do instead is notice that:
                            $$sum^{i=k+1}_{i=1} i^2= underbrace{frac{k(k+1)(2k+1)}{6}}_{text{sum of k terms}} + underbrace{(k+1)^2}_{text{(k+1)th term}}$$
                            $$sum^{i=k+1}_{i=1} i^2= frac{k(k+1)(2k+1)}{6}+frac{6(k+1)^2}{6}$$
                            $$sum^{i=k+1}_{i=1} i^2= frac{(k+1)left(k(2k+1)+6(k+1)right)}{6}$$
                            $$sum^{i=k+1}_{i=1} i^2= frac{(k+1)(2k^2+color{green}{7k}+6)}{6}=frac{(k+1)(2k^2+color{green}{4k+3k}+6)}{6}=frac{(k+1)left(2k(k+2)+3(k+2)right)}{6}=color{blue}{frac{(k+1)(k+2)(2k+3)}{6}}quad forall space k in mathbb{N}$$



                            Which is the relation we set out to prove. So the method is to substitute $i=k+1$ into the formula you are trying to prove and then use the inductive assumption to recover the $color{blue}{mathrm{blue}}$ equation at the end.






                            share|cite|improve this answer











                            $endgroup$





















                              0












                              $begingroup$

                              Here is a sketch with calculus.



                              $f(x) = x^2$ is a strictly monotonously increasing function. The sum is an upper Riemann sum of width 1 of this function. But if we shift it down one step we get a lower Riemann sum of width 1. The difference in integral is $$int_{n-1}^n f(x)dx - int_0^1 f(x)dx = n^3/3 - (n-3)^3/3 - 1 = n^2-3n-4$$





                              This is not quite $n^2$, but we can now turn the question into asking "if we had an offset in the integration, say $+alpha$ on each "step", what $alpha$ should we select to get as close to $n^2$ as possible?"



                              This is not a full answer, but intends on helping how to think to try and solve problems.






                              share|cite|improve this answer









                              $endgroup$





















                                0












                                $begingroup$

                                Firstly, calculate the sum $S=sum_{k=1}^n k(k+1)$ which is:



                                $S=1cdot 2+2cdot 3+ cdots +n(n+1)$,



                                multiplying $S$ by 3
                                we get:



                                $3S=1cdot 2cdot 3+2cdot 3cdot (4-1)+3cdot 4cdot (5-2)+ cdots +ncdot (n+1)cdot (n+2-(n-1))$



                                $3S=1 · 2 · 3 + 2 · 3 · 4 − 1 · 2 · 3 + 3 · 4 · 5 − 2 · 3 · 4 + · · ·
                                + n(n + 1)(n + 2) − (n − 1)n(n + 1)$



                                This telescoping series collapses to yield:



                                $$3S=n(n+1)(n+2)$$



                                $$S=frac{n(n+1)(n+2)}{3}$$



                                On the other side we have:



                                begin{alignat*}{2}
                                &sum_{k=1}^n k(k+1)&&=sum_{k=1}^n k^2+k \
                                & &&=sum_{k=1}^n k^2+sum_{k=1}^n k \
                                &frac{n(n+1)(n+2)}{3}&&=sum_{k=1}^n k^2+frac{n(n+1)}{2} \
                                &sum_{k=1}^n k^2&&=frac{n(n+1)(n+2)}{3}-frac{n(n+1)}{2} \
                                &sum_{k=1}^n k^2&&=frac{n(n+1)(2n+1)}{6}
                                end{alignat*}






                                share|cite|improve this answer











                                $endgroup$





















                                  0












                                  $begingroup$

                                  It is a quadraic sequence as 1,4,9,16,25,36 ........//



                                  Its first term (a)=1
                                  1st difference (d)=4-1=3
                                  2nd difference i.e. constant difference(c)=2



                                  There is a sum formula for any quadraic equation which is



                                  Sn=n/6*[(n-1)3d+(n-1)(n-2)c]+an



                                  Putting above value in this formula,we get



                                  Sn=n/6*[(n-1)3*3+(n^2-3n+2)2]+1n



                                   =n/6[9n-9+2n^2-6n+4]+n

                                  =n/6[2n^2+3n-5]+n

                                  =n/6[2n^2+3n-5+6]

                                  =n/6[2n^2+3n+1]

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


                                  Which is final answer.There is also sum formula for cubic and even quartic sequence.






                                  share|cite|improve this answer











                                  $endgroup$









                                  • 1




                                    $begingroup$
                                    Why is the sum formula true then?
                                    $endgroup$
                                    – Alex Vong
                                    May 19 '18 at 17:00










                                  • $begingroup$
                                    @AlexVong This formula is made by myself using a long theory of sequence.Combining arithmetic sequence formula it is formed
                                    $endgroup$
                                    – Santosh kurmi
                                    May 19 '18 at 17:22












                                  • $begingroup$
                                    It is real sum formula of quadraic sequence
                                    $endgroup$
                                    – Santosh kurmi
                                    May 19 '18 at 17:26










                                  • $begingroup$
                                    @AlexVong It is made using Sum formula of AP
                                    $endgroup$
                                    – Santosh kurmi
                                    May 19 '18 at 17:27










                                  • $begingroup$
                                    Since the question asked why the formula is true, you may want to add the reason to the answer.
                                    $endgroup$
                                    – Alex Vong
                                    May 20 '18 at 5:58



















                                  -1












                                  $begingroup$

                                  Another method by using telescoping sum :-
                                  We know $(a+b)^3-a^3-b^3=3ab(a+b)$ , take



                                  $a=k-1 , b=2$ , then $a+b=k+1$ and $(k+1)^3-(k-1)^3-2^3=6(k-1)(k+1)=6k^2-6$ ,



                                  hence $(k+1)^3-(k-1)^3-8+6=(k+1)^3-k^3+k^3-(k-1)^3-2=6k^2$ , taking sum over $k$



                                  from $1$ to $n$ we get , $sum_{k=1}^n [(k+1)^3-k^3] + sum_{k=1}^n [k^3-(k-1)^3] -sum_{k=1}^n 2 = 6 sum_{k=1}^nk^2$ , the first



                                  sum on the left hand side is telescoping resulting in $(n+1)^3-1$ , the second sum is also telescoping resulting in $n^3-(1-1)^3=n^3$ , and the third sum is simply $2n$ , hence



                                  $6 sum_{k=1}^nk^2=(n+1)^3-1+n^3-2n=2n^3+3n^2+n=n(n+1)(2n+1)$






                                  share|cite|improve this answer









                                  $endgroup$





















                                    -1












                                    $begingroup$

                                    If you know that the nth square is the sum of the first n odd numbers, you can rewrite each square in the above sum in that way and do a little bit of rearranging to get the desired identity. In general, knowing the value of (n + 1)^k - n^k allows you to write (n+1)^k as a telescoping sum of a polynomial of degree k-1, running over the values 1 through n. If you know the values of the sums of consecutive powers up to k-1, this allows you to find the sum of consecutive kth powers by substituting the polynomial sum for each kth power.






                                    share|cite|improve this answer











                                    $endgroup$












                                      protected by Jyrki Lahtonen May 19 '18 at 17:31



                                      Thank you for your interest in this question.
                                      Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).



                                      Would you like to answer one of these unanswered questions instead?














                                      30 Answers
                                      30






                                      active

                                      oldest

                                      votes








                                      30 Answers
                                      30






                                      active

                                      oldest

                                      votes









                                      active

                                      oldest

                                      votes






                                      active

                                      oldest

                                      votes









                                      62












                                      $begingroup$

                                      You can easily prove it by induction.



                                      One way to find the coefficients, assuming we already know that it's a degree $3$ polynomial, is to calculate the sum for $n=0,1,2,3$. This gives us four values of a degree $3$ polynomial, and so we can find it.



                                      The better way to approach it, though, is through the identity
                                      $$ sum_{t=0}^n binom{t}{k} = binom{n+1}{k+1}. $$
                                      This identity is true since in order to choose a $(k+1)$-subset of $n+1$, you first choose an element $t+1$, and then a $k$-subset of $t$.



                                      We therefore know that
                                      $$ sum_{t=0}^n A + Bt + Cbinom{t}{2} = A(n+1) + Bbinom{n+1}{2} + Cbinom{n+1}{3}. $$
                                      Now choosing $A=0,B=1,C=2$, we have
                                      $$ A+Bt + Cbinom{t}{2} = t^2. $$
                                      Therefore the sum is equal to
                                      $$ binom{n+1}{2} + 2binom{n+1}{3}. $$






                                      share|cite|improve this answer









                                      $endgroup$













                                      • $begingroup$
                                        That's a good method: +1! Concerning the polynomial approach, I think it could be enhanced by noticing that if $p_k(n)=sum_{i=1}^n i^k$ then, extending what you wrote, $p_kinmathbb Q[n]$, $partial p_k=k+1$, and $n(n+1),Big|,p_k$ for every $k$. For $k=2$ this reduces to 2 the coefficients to be found making this approach equally worth, isn't it?
                                        $endgroup$
                                        – AndreasT
                                        Mar 30 '13 at 15:58










                                      • $begingroup$
                                        That's a great approach. Can you tell me what's the name of this identity : $sum_{t=0}^n binom{t}{k} = binom{n+1}{k+1}$. Is it the Pascal triangle?
                                        $endgroup$
                                        – hlapointe
                                        Oct 21 '15 at 14:37






                                      • 1




                                        $begingroup$
                                        @hlapointe It probably does have a name but I can't think of any! Do let me know if you find out.
                                        $endgroup$
                                        – Yuval Filmus
                                        Oct 21 '15 at 15:27






                                      • 5




                                        $begingroup$
                                        I learned this as the hockey stick identity.
                                        $endgroup$
                                        – Slade
                                        Jan 11 '16 at 9:09
















                                      62












                                      $begingroup$

                                      You can easily prove it by induction.



                                      One way to find the coefficients, assuming we already know that it's a degree $3$ polynomial, is to calculate the sum for $n=0,1,2,3$. This gives us four values of a degree $3$ polynomial, and so we can find it.



                                      The better way to approach it, though, is through the identity
                                      $$ sum_{t=0}^n binom{t}{k} = binom{n+1}{k+1}. $$
                                      This identity is true since in order to choose a $(k+1)$-subset of $n+1$, you first choose an element $t+1$, and then a $k$-subset of $t$.



                                      We therefore know that
                                      $$ sum_{t=0}^n A + Bt + Cbinom{t}{2} = A(n+1) + Bbinom{n+1}{2} + Cbinom{n+1}{3}. $$
                                      Now choosing $A=0,B=1,C=2$, we have
                                      $$ A+Bt + Cbinom{t}{2} = t^2. $$
                                      Therefore the sum is equal to
                                      $$ binom{n+1}{2} + 2binom{n+1}{3}. $$






                                      share|cite|improve this answer









                                      $endgroup$













                                      • $begingroup$
                                        That's a good method: +1! Concerning the polynomial approach, I think it could be enhanced by noticing that if $p_k(n)=sum_{i=1}^n i^k$ then, extending what you wrote, $p_kinmathbb Q[n]$, $partial p_k=k+1$, and $n(n+1),Big|,p_k$ for every $k$. For $k=2$ this reduces to 2 the coefficients to be found making this approach equally worth, isn't it?
                                        $endgroup$
                                        – AndreasT
                                        Mar 30 '13 at 15:58










                                      • $begingroup$
                                        That's a great approach. Can you tell me what's the name of this identity : $sum_{t=0}^n binom{t}{k} = binom{n+1}{k+1}$. Is it the Pascal triangle?
                                        $endgroup$
                                        – hlapointe
                                        Oct 21 '15 at 14:37






                                      • 1




                                        $begingroup$
                                        @hlapointe It probably does have a name but I can't think of any! Do let me know if you find out.
                                        $endgroup$
                                        – Yuval Filmus
                                        Oct 21 '15 at 15:27






                                      • 5




                                        $begingroup$
                                        I learned this as the hockey stick identity.
                                        $endgroup$
                                        – Slade
                                        Jan 11 '16 at 9:09














                                      62












                                      62








                                      62





                                      $begingroup$

                                      You can easily prove it by induction.



                                      One way to find the coefficients, assuming we already know that it's a degree $3$ polynomial, is to calculate the sum for $n=0,1,2,3$. This gives us four values of a degree $3$ polynomial, and so we can find it.



                                      The better way to approach it, though, is through the identity
                                      $$ sum_{t=0}^n binom{t}{k} = binom{n+1}{k+1}. $$
                                      This identity is true since in order to choose a $(k+1)$-subset of $n+1$, you first choose an element $t+1$, and then a $k$-subset of $t$.



                                      We therefore know that
                                      $$ sum_{t=0}^n A + Bt + Cbinom{t}{2} = A(n+1) + Bbinom{n+1}{2} + Cbinom{n+1}{3}. $$
                                      Now choosing $A=0,B=1,C=2$, we have
                                      $$ A+Bt + Cbinom{t}{2} = t^2. $$
                                      Therefore the sum is equal to
                                      $$ binom{n+1}{2} + 2binom{n+1}{3}. $$






                                      share|cite|improve this answer









                                      $endgroup$



                                      You can easily prove it by induction.



                                      One way to find the coefficients, assuming we already know that it's a degree $3$ polynomial, is to calculate the sum for $n=0,1,2,3$. This gives us four values of a degree $3$ polynomial, and so we can find it.



                                      The better way to approach it, though, is through the identity
                                      $$ sum_{t=0}^n binom{t}{k} = binom{n+1}{k+1}. $$
                                      This identity is true since in order to choose a $(k+1)$-subset of $n+1$, you first choose an element $t+1$, and then a $k$-subset of $t$.



                                      We therefore know that
                                      $$ sum_{t=0}^n A + Bt + Cbinom{t}{2} = A(n+1) + Bbinom{n+1}{2} + Cbinom{n+1}{3}. $$
                                      Now choosing $A=0,B=1,C=2$, we have
                                      $$ A+Bt + Cbinom{t}{2} = t^2. $$
                                      Therefore the sum is equal to
                                      $$ binom{n+1}{2} + 2binom{n+1}{3}. $$







                                      share|cite|improve this answer












                                      share|cite|improve this answer



                                      share|cite|improve this answer










                                      answered Jun 27 '11 at 23:16









                                      Yuval FilmusYuval Filmus

                                      48.4k471144




                                      48.4k471144












                                      • $begingroup$
                                        That's a good method: +1! Concerning the polynomial approach, I think it could be enhanced by noticing that if $p_k(n)=sum_{i=1}^n i^k$ then, extending what you wrote, $p_kinmathbb Q[n]$, $partial p_k=k+1$, and $n(n+1),Big|,p_k$ for every $k$. For $k=2$ this reduces to 2 the coefficients to be found making this approach equally worth, isn't it?
                                        $endgroup$
                                        – AndreasT
                                        Mar 30 '13 at 15:58










                                      • $begingroup$
                                        That's a great approach. Can you tell me what's the name of this identity : $sum_{t=0}^n binom{t}{k} = binom{n+1}{k+1}$. Is it the Pascal triangle?
                                        $endgroup$
                                        – hlapointe
                                        Oct 21 '15 at 14:37






                                      • 1




                                        $begingroup$
                                        @hlapointe It probably does have a name but I can't think of any! Do let me know if you find out.
                                        $endgroup$
                                        – Yuval Filmus
                                        Oct 21 '15 at 15:27






                                      • 5




                                        $begingroup$
                                        I learned this as the hockey stick identity.
                                        $endgroup$
                                        – Slade
                                        Jan 11 '16 at 9:09


















                                      • $begingroup$
                                        That's a good method: +1! Concerning the polynomial approach, I think it could be enhanced by noticing that if $p_k(n)=sum_{i=1}^n i^k$ then, extending what you wrote, $p_kinmathbb Q[n]$, $partial p_k=k+1$, and $n(n+1),Big|,p_k$ for every $k$. For $k=2$ this reduces to 2 the coefficients to be found making this approach equally worth, isn't it?
                                        $endgroup$
                                        – AndreasT
                                        Mar 30 '13 at 15:58










                                      • $begingroup$
                                        That's a great approach. Can you tell me what's the name of this identity : $sum_{t=0}^n binom{t}{k} = binom{n+1}{k+1}$. Is it the Pascal triangle?
                                        $endgroup$
                                        – hlapointe
                                        Oct 21 '15 at 14:37






                                      • 1




                                        $begingroup$
                                        @hlapointe It probably does have a name but I can't think of any! Do let me know if you find out.
                                        $endgroup$
                                        – Yuval Filmus
                                        Oct 21 '15 at 15:27






                                      • 5




                                        $begingroup$
                                        I learned this as the hockey stick identity.
                                        $endgroup$
                                        – Slade
                                        Jan 11 '16 at 9:09
















                                      $begingroup$
                                      That's a good method: +1! Concerning the polynomial approach, I think it could be enhanced by noticing that if $p_k(n)=sum_{i=1}^n i^k$ then, extending what you wrote, $p_kinmathbb Q[n]$, $partial p_k=k+1$, and $n(n+1),Big|,p_k$ for every $k$. For $k=2$ this reduces to 2 the coefficients to be found making this approach equally worth, isn't it?
                                      $endgroup$
                                      – AndreasT
                                      Mar 30 '13 at 15:58




                                      $begingroup$
                                      That's a good method: +1! Concerning the polynomial approach, I think it could be enhanced by noticing that if $p_k(n)=sum_{i=1}^n i^k$ then, extending what you wrote, $p_kinmathbb Q[n]$, $partial p_k=k+1$, and $n(n+1),Big|,p_k$ for every $k$. For $k=2$ this reduces to 2 the coefficients to be found making this approach equally worth, isn't it?
                                      $endgroup$
                                      – AndreasT
                                      Mar 30 '13 at 15:58












                                      $begingroup$
                                      That's a great approach. Can you tell me what's the name of this identity : $sum_{t=0}^n binom{t}{k} = binom{n+1}{k+1}$. Is it the Pascal triangle?
                                      $endgroup$
                                      – hlapointe
                                      Oct 21 '15 at 14:37




                                      $begingroup$
                                      That's a great approach. Can you tell me what's the name of this identity : $sum_{t=0}^n binom{t}{k} = binom{n+1}{k+1}$. Is it the Pascal triangle?
                                      $endgroup$
                                      – hlapointe
                                      Oct 21 '15 at 14:37




                                      1




                                      1




                                      $begingroup$
                                      @hlapointe It probably does have a name but I can't think of any! Do let me know if you find out.
                                      $endgroup$
                                      – Yuval Filmus
                                      Oct 21 '15 at 15:27




                                      $begingroup$
                                      @hlapointe It probably does have a name but I can't think of any! Do let me know if you find out.
                                      $endgroup$
                                      – Yuval Filmus
                                      Oct 21 '15 at 15:27




                                      5




                                      5




                                      $begingroup$
                                      I learned this as the hockey stick identity.
                                      $endgroup$
                                      – Slade
                                      Jan 11 '16 at 9:09




                                      $begingroup$
                                      I learned this as the hockey stick identity.
                                      $endgroup$
                                      – Slade
                                      Jan 11 '16 at 9:09











                                      135












                                      $begingroup$

                                      Another way (by Euler, I think), from the geometric sum:



                                      $$1 + x + x^2 + cdots + x^n = frac{x^{n+1}-1}{x-1}$$



                                      Differentiate both sides and multiply by $x$:



                                      $$x + 2 x^2 + 3 x^3 + cdots + n x^{n} = frac{n x^{n+2}-(n+1) x^{n+1} +x}{(x-1)^2}$$



                                      Differentiating once more, we get on the LHS



                                      $$1 + 2^2 x + 3^2 x^2 + cdots + n^2 x^{n-1}$$



                                      which, evaluated at $x=1$ gives our sum $sum_{k=1}^n k^2$. What remains (straightforward, but tedious) is to compute the derivative on the RHS, and evaluate it at $x to 1$ (eg, with L'Hopital rule).



                                      It should be evident that this procedure also can be applied (though it also turns more cumbersome) for sums of higher powers.





                                      (Update) here's a concrete derivation, using binomial expansion of the RHS around $(x-1)$:



                                      $$g(x)=frac{x^{n+1}-1}{x-1}=frac{left(left(x-1right)+1right)^{n+1}-1}{x-1}=\=(n+1)+{n+1 choose 2}(x-1)+{n+1 choose 3}(x-1)^2+Oleft((x-1)^3right)$$



                                      Hence $$(g'(x) , x)'={n+1 choose 2}+{n+1 choose 3}2 x + O(x-1)$$
                                      which evaluated at $x=1$ gives the desired answer.



                                      Applying the same procedure for higher powers, we get, for example:
                                      $$ sum_{k=1}^n k^3={n+1 choose 2}+{n+1 choose 3}6+{n+1 choose 4}6$$






                                      share|cite|improve this answer











                                      $endgroup$









                                      • 11




                                        $begingroup$
                                        I must admit I didn't know this one even though the problem is quite popular. +1
                                        $endgroup$
                                        – Patrick Da Silva
                                        Jul 10 '11 at 1:33






                                      • 3




                                        $begingroup$
                                        So slick I laughed reading this!
                                        $endgroup$
                                        – ttt
                                        Jul 10 '11 at 16:54






                                      • 9




                                        $begingroup$
                                        I waited in order to gain the commenting privilege just to say this : You made me fall in love with calculus again !!
                                        $endgroup$
                                        – BS.
                                        Jul 11 '11 at 2:10










                                      • $begingroup$
                                        @leonbloy Interesting! Will look at this tomorrow!
                                        $endgroup$
                                        – Pedro Tamaroff
                                        Mar 24 '12 at 6:48










                                      • $begingroup$
                                        Really nice! +1
                                        $endgroup$
                                        – AndreasT
                                        Mar 30 '13 at 15:47
















                                      135












                                      $begingroup$

                                      Another way (by Euler, I think), from the geometric sum:



                                      $$1 + x + x^2 + cdots + x^n = frac{x^{n+1}-1}{x-1}$$



                                      Differentiate both sides and multiply by $x$:



                                      $$x + 2 x^2 + 3 x^3 + cdots + n x^{n} = frac{n x^{n+2}-(n+1) x^{n+1} +x}{(x-1)^2}$$



                                      Differentiating once more, we get on the LHS



                                      $$1 + 2^2 x + 3^2 x^2 + cdots + n^2 x^{n-1}$$



                                      which, evaluated at $x=1$ gives our sum $sum_{k=1}^n k^2$. What remains (straightforward, but tedious) is to compute the derivative on the RHS, and evaluate it at $x to 1$ (eg, with L'Hopital rule).



                                      It should be evident that this procedure also can be applied (though it also turns more cumbersome) for sums of higher powers.





                                      (Update) here's a concrete derivation, using binomial expansion of the RHS around $(x-1)$:



                                      $$g(x)=frac{x^{n+1}-1}{x-1}=frac{left(left(x-1right)+1right)^{n+1}-1}{x-1}=\=(n+1)+{n+1 choose 2}(x-1)+{n+1 choose 3}(x-1)^2+Oleft((x-1)^3right)$$



                                      Hence $$(g'(x) , x)'={n+1 choose 2}+{n+1 choose 3}2 x + O(x-1)$$
                                      which evaluated at $x=1$ gives the desired answer.



                                      Applying the same procedure for higher powers, we get, for example:
                                      $$ sum_{k=1}^n k^3={n+1 choose 2}+{n+1 choose 3}6+{n+1 choose 4}6$$






                                      share|cite|improve this answer











                                      $endgroup$









                                      • 11




                                        $begingroup$
                                        I must admit I didn't know this one even though the problem is quite popular. +1
                                        $endgroup$
                                        – Patrick Da Silva
                                        Jul 10 '11 at 1:33






                                      • 3




                                        $begingroup$
                                        So slick I laughed reading this!
                                        $endgroup$
                                        – ttt
                                        Jul 10 '11 at 16:54






                                      • 9




                                        $begingroup$
                                        I waited in order to gain the commenting privilege just to say this : You made me fall in love with calculus again !!
                                        $endgroup$
                                        – BS.
                                        Jul 11 '11 at 2:10










                                      • $begingroup$
                                        @leonbloy Interesting! Will look at this tomorrow!
                                        $endgroup$
                                        – Pedro Tamaroff
                                        Mar 24 '12 at 6:48










                                      • $begingroup$
                                        Really nice! +1
                                        $endgroup$
                                        – AndreasT
                                        Mar 30 '13 at 15:47














                                      135












                                      135








                                      135





                                      $begingroup$

                                      Another way (by Euler, I think), from the geometric sum:



                                      $$1 + x + x^2 + cdots + x^n = frac{x^{n+1}-1}{x-1}$$



                                      Differentiate both sides and multiply by $x$:



                                      $$x + 2 x^2 + 3 x^3 + cdots + n x^{n} = frac{n x^{n+2}-(n+1) x^{n+1} +x}{(x-1)^2}$$



                                      Differentiating once more, we get on the LHS



                                      $$1 + 2^2 x + 3^2 x^2 + cdots + n^2 x^{n-1}$$



                                      which, evaluated at $x=1$ gives our sum $sum_{k=1}^n k^2$. What remains (straightforward, but tedious) is to compute the derivative on the RHS, and evaluate it at $x to 1$ (eg, with L'Hopital rule).



                                      It should be evident that this procedure also can be applied (though it also turns more cumbersome) for sums of higher powers.





                                      (Update) here's a concrete derivation, using binomial expansion of the RHS around $(x-1)$:



                                      $$g(x)=frac{x^{n+1}-1}{x-1}=frac{left(left(x-1right)+1right)^{n+1}-1}{x-1}=\=(n+1)+{n+1 choose 2}(x-1)+{n+1 choose 3}(x-1)^2+Oleft((x-1)^3right)$$



                                      Hence $$(g'(x) , x)'={n+1 choose 2}+{n+1 choose 3}2 x + O(x-1)$$
                                      which evaluated at $x=1$ gives the desired answer.



                                      Applying the same procedure for higher powers, we get, for example:
                                      $$ sum_{k=1}^n k^3={n+1 choose 2}+{n+1 choose 3}6+{n+1 choose 4}6$$






                                      share|cite|improve this answer











                                      $endgroup$



                                      Another way (by Euler, I think), from the geometric sum:



                                      $$1 + x + x^2 + cdots + x^n = frac{x^{n+1}-1}{x-1}$$



                                      Differentiate both sides and multiply by $x$:



                                      $$x + 2 x^2 + 3 x^3 + cdots + n x^{n} = frac{n x^{n+2}-(n+1) x^{n+1} +x}{(x-1)^2}$$



                                      Differentiating once more, we get on the LHS



                                      $$1 + 2^2 x + 3^2 x^2 + cdots + n^2 x^{n-1}$$



                                      which, evaluated at $x=1$ gives our sum $sum_{k=1}^n k^2$. What remains (straightforward, but tedious) is to compute the derivative on the RHS, and evaluate it at $x to 1$ (eg, with L'Hopital rule).



                                      It should be evident that this procedure also can be applied (though it also turns more cumbersome) for sums of higher powers.





                                      (Update) here's a concrete derivation, using binomial expansion of the RHS around $(x-1)$:



                                      $$g(x)=frac{x^{n+1}-1}{x-1}=frac{left(left(x-1right)+1right)^{n+1}-1}{x-1}=\=(n+1)+{n+1 choose 2}(x-1)+{n+1 choose 3}(x-1)^2+Oleft((x-1)^3right)$$



                                      Hence $$(g'(x) , x)'={n+1 choose 2}+{n+1 choose 3}2 x + O(x-1)$$
                                      which evaluated at $x=1$ gives the desired answer.



                                      Applying the same procedure for higher powers, we get, for example:
                                      $$ sum_{k=1}^n k^3={n+1 choose 2}+{n+1 choose 3}6+{n+1 choose 4}6$$







                                      share|cite|improve this answer














                                      share|cite|improve this answer



                                      share|cite|improve this answer








                                      edited Oct 24 '18 at 2:16

























                                      answered Jun 28 '11 at 14:28









                                      leonbloyleonbloy

                                      40.5k645107




                                      40.5k645107








                                      • 11




                                        $begingroup$
                                        I must admit I didn't know this one even though the problem is quite popular. +1
                                        $endgroup$
                                        – Patrick Da Silva
                                        Jul 10 '11 at 1:33






                                      • 3




                                        $begingroup$
                                        So slick I laughed reading this!
                                        $endgroup$
                                        – ttt
                                        Jul 10 '11 at 16:54






                                      • 9




                                        $begingroup$
                                        I waited in order to gain the commenting privilege just to say this : You made me fall in love with calculus again !!
                                        $endgroup$
                                        – BS.
                                        Jul 11 '11 at 2:10










                                      • $begingroup$
                                        @leonbloy Interesting! Will look at this tomorrow!
                                        $endgroup$
                                        – Pedro Tamaroff
                                        Mar 24 '12 at 6:48










                                      • $begingroup$
                                        Really nice! +1
                                        $endgroup$
                                        – AndreasT
                                        Mar 30 '13 at 15:47














                                      • 11




                                        $begingroup$
                                        I must admit I didn't know this one even though the problem is quite popular. +1
                                        $endgroup$
                                        – Patrick Da Silva
                                        Jul 10 '11 at 1:33






                                      • 3




                                        $begingroup$
                                        So slick I laughed reading this!
                                        $endgroup$
                                        – ttt
                                        Jul 10 '11 at 16:54






                                      • 9




                                        $begingroup$
                                        I waited in order to gain the commenting privilege just to say this : You made me fall in love with calculus again !!
                                        $endgroup$
                                        – BS.
                                        Jul 11 '11 at 2:10










                                      • $begingroup$
                                        @leonbloy Interesting! Will look at this tomorrow!
                                        $endgroup$
                                        – Pedro Tamaroff
                                        Mar 24 '12 at 6:48










                                      • $begingroup$
                                        Really nice! +1
                                        $endgroup$
                                        – AndreasT
                                        Mar 30 '13 at 15:47








                                      11




                                      11




                                      $begingroup$
                                      I must admit I didn't know this one even though the problem is quite popular. +1
                                      $endgroup$
                                      – Patrick Da Silva
                                      Jul 10 '11 at 1:33




                                      $begingroup$
                                      I must admit I didn't know this one even though the problem is quite popular. +1
                                      $endgroup$
                                      – Patrick Da Silva
                                      Jul 10 '11 at 1:33




                                      3




                                      3




                                      $begingroup$
                                      So slick I laughed reading this!
                                      $endgroup$
                                      – ttt
                                      Jul 10 '11 at 16:54




                                      $begingroup$
                                      So slick I laughed reading this!
                                      $endgroup$
                                      – ttt
                                      Jul 10 '11 at 16:54




                                      9




                                      9




                                      $begingroup$
                                      I waited in order to gain the commenting privilege just to say this : You made me fall in love with calculus again !!
                                      $endgroup$
                                      – BS.
                                      Jul 11 '11 at 2:10




                                      $begingroup$
                                      I waited in order to gain the commenting privilege just to say this : You made me fall in love with calculus again !!
                                      $endgroup$
                                      – BS.
                                      Jul 11 '11 at 2:10












                                      $begingroup$
                                      @leonbloy Interesting! Will look at this tomorrow!
                                      $endgroup$
                                      – Pedro Tamaroff
                                      Mar 24 '12 at 6:48




                                      $begingroup$
                                      @leonbloy Interesting! Will look at this tomorrow!
                                      $endgroup$
                                      – Pedro Tamaroff
                                      Mar 24 '12 at 6:48












                                      $begingroup$
                                      Really nice! +1
                                      $endgroup$
                                      – AndreasT
                                      Mar 30 '13 at 15:47




                                      $begingroup$
                                      Really nice! +1
                                      $endgroup$
                                      – AndreasT
                                      Mar 30 '13 at 15:47











                                      67












                                      $begingroup$

                                      I like this visual proof, due to Man-Keung Siu. It appeared in the March 1984 issue of Mathematics Magazine.



                                      enter image description here



                                      See also two more proofs (as well as this one) in Roger Nelson's Proofs Without Words: Exercises in Visual Thinking.






                                      share|cite|improve this answer









                                      $endgroup$









                                      • 1




                                        $begingroup$
                                        In a similar vein are most posts in this MO-thread. Incidentally, another Mike posted Man-Keung Siu's proof there.
                                        $endgroup$
                                        – t.b.
                                        Jun 28 '11 at 5:21










                                      • $begingroup$
                                        Beautiful extension of the classic Gauss sum proof - I love this one!
                                        $endgroup$
                                        – Steven Stadnicki
                                        Oct 28 '11 at 22:20
















                                      67












                                      $begingroup$

                                      I like this visual proof, due to Man-Keung Siu. It appeared in the March 1984 issue of Mathematics Magazine.



                                      enter image description here



                                      See also two more proofs (as well as this one) in Roger Nelson's Proofs Without Words: Exercises in Visual Thinking.






                                      share|cite|improve this answer









                                      $endgroup$









                                      • 1




                                        $begingroup$
                                        In a similar vein are most posts in this MO-thread. Incidentally, another Mike posted Man-Keung Siu's proof there.
                                        $endgroup$
                                        – t.b.
                                        Jun 28 '11 at 5:21










                                      • $begingroup$
                                        Beautiful extension of the classic Gauss sum proof - I love this one!
                                        $endgroup$
                                        – Steven Stadnicki
                                        Oct 28 '11 at 22:20














                                      67












                                      67








                                      67





                                      $begingroup$

                                      I like this visual proof, due to Man-Keung Siu. It appeared in the March 1984 issue of Mathematics Magazine.



                                      enter image description here



                                      See also two more proofs (as well as this one) in Roger Nelson's Proofs Without Words: Exercises in Visual Thinking.






                                      share|cite|improve this answer









                                      $endgroup$



                                      I like this visual proof, due to Man-Keung Siu. It appeared in the March 1984 issue of Mathematics Magazine.



                                      enter image description here



                                      See also two more proofs (as well as this one) in Roger Nelson's Proofs Without Words: Exercises in Visual Thinking.







                                      share|cite|improve this answer












                                      share|cite|improve this answer



                                      share|cite|improve this answer










                                      answered Jun 28 '11 at 5:10









                                      Mike SpiveyMike Spivey

                                      42.4k8141232




                                      42.4k8141232








                                      • 1




                                        $begingroup$
                                        In a similar vein are most posts in this MO-thread. Incidentally, another Mike posted Man-Keung Siu's proof there.
                                        $endgroup$
                                        – t.b.
                                        Jun 28 '11 at 5:21










                                      • $begingroup$
                                        Beautiful extension of the classic Gauss sum proof - I love this one!
                                        $endgroup$
                                        – Steven Stadnicki
                                        Oct 28 '11 at 22:20














                                      • 1




                                        $begingroup$
                                        In a similar vein are most posts in this MO-thread. Incidentally, another Mike posted Man-Keung Siu's proof there.
                                        $endgroup$
                                        – t.b.
                                        Jun 28 '11 at 5:21










                                      • $begingroup$
                                        Beautiful extension of the classic Gauss sum proof - I love this one!
                                        $endgroup$
                                        – Steven Stadnicki
                                        Oct 28 '11 at 22:20








                                      1




                                      1




                                      $begingroup$
                                      In a similar vein are most posts in this MO-thread. Incidentally, another Mike posted Man-Keung Siu's proof there.
                                      $endgroup$
                                      – t.b.
                                      Jun 28 '11 at 5:21




                                      $begingroup$
                                      In a similar vein are most posts in this MO-thread. Incidentally, another Mike posted Man-Keung Siu's proof there.
                                      $endgroup$
                                      – t.b.
                                      Jun 28 '11 at 5:21












                                      $begingroup$
                                      Beautiful extension of the classic Gauss sum proof - I love this one!
                                      $endgroup$
                                      – Steven Stadnicki
                                      Oct 28 '11 at 22:20




                                      $begingroup$
                                      Beautiful extension of the classic Gauss sum proof - I love this one!
                                      $endgroup$
                                      – Steven Stadnicki
                                      Oct 28 '11 at 22:20











                                      40












                                      $begingroup$

                                      Yet another proof(!)



                                      Notice that $(k+1)^3 - k^3 = 3k^2 + 3k + 1$ and hence



                                      $$(n+1)^3 = sum_{k=0}^n left[ (k+1)^3 - k^3right] = 3sum_{k=0}^n k^2 + 3sum_{k=0}^n k + sum_{k=0}^n 1$$



                                      which gives you



                                      $$begin{align}
                                      sum_{k=1}^n k^2
                                      & = frac{1}{3}(n+1)^3 - frac{1}{2}n(n+1) - frac{1}{3}(n+1) \
                                      & = frac{1}{6}(n+1) left[ 2(n+1)^2 - 3n - 2right] \
                                      & = frac{1}{6}(n+1)(2n^2 +n) \
                                      & = frac{1}{6}n(n+1)(2n+1)
                                      end{align}$$






                                      share|cite|improve this answer











                                      $endgroup$









                                      • 4




                                        $begingroup$
                                        The appeal of this proof is that it's sort of the discrete counterpart to the integral: $int_0^n x^2 dx= n^3/3$
                                        $endgroup$
                                        – leonbloy
                                        Jan 14 '13 at 19:35
















                                      40












                                      $begingroup$

                                      Yet another proof(!)



                                      Notice that $(k+1)^3 - k^3 = 3k^2 + 3k + 1$ and hence



                                      $$(n+1)^3 = sum_{k=0}^n left[ (k+1)^3 - k^3right] = 3sum_{k=0}^n k^2 + 3sum_{k=0}^n k + sum_{k=0}^n 1$$



                                      which gives you



                                      $$begin{align}
                                      sum_{k=1}^n k^2
                                      & = frac{1}{3}(n+1)^3 - frac{1}{2}n(n+1) - frac{1}{3}(n+1) \
                                      & = frac{1}{6}(n+1) left[ 2(n+1)^2 - 3n - 2right] \
                                      & = frac{1}{6}(n+1)(2n^2 +n) \
                                      & = frac{1}{6}n(n+1)(2n+1)
                                      end{align}$$






                                      share|cite|improve this answer











                                      $endgroup$









                                      • 4




                                        $begingroup$
                                        The appeal of this proof is that it's sort of the discrete counterpart to the integral: $int_0^n x^2 dx= n^3/3$
                                        $endgroup$
                                        – leonbloy
                                        Jan 14 '13 at 19:35














                                      40












                                      40








                                      40





                                      $begingroup$

                                      Yet another proof(!)



                                      Notice that $(k+1)^3 - k^3 = 3k^2 + 3k + 1$ and hence



                                      $$(n+1)^3 = sum_{k=0}^n left[ (k+1)^3 - k^3right] = 3sum_{k=0}^n k^2 + 3sum_{k=0}^n k + sum_{k=0}^n 1$$



                                      which gives you



                                      $$begin{align}
                                      sum_{k=1}^n k^2
                                      & = frac{1}{3}(n+1)^3 - frac{1}{2}n(n+1) - frac{1}{3}(n+1) \
                                      & = frac{1}{6}(n+1) left[ 2(n+1)^2 - 3n - 2right] \
                                      & = frac{1}{6}(n+1)(2n^2 +n) \
                                      & = frac{1}{6}n(n+1)(2n+1)
                                      end{align}$$






                                      share|cite|improve this answer











                                      $endgroup$



                                      Yet another proof(!)



                                      Notice that $(k+1)^3 - k^3 = 3k^2 + 3k + 1$ and hence



                                      $$(n+1)^3 = sum_{k=0}^n left[ (k+1)^3 - k^3right] = 3sum_{k=0}^n k^2 + 3sum_{k=0}^n k + sum_{k=0}^n 1$$



                                      which gives you



                                      $$begin{align}
                                      sum_{k=1}^n k^2
                                      & = frac{1}{3}(n+1)^3 - frac{1}{2}n(n+1) - frac{1}{3}(n+1) \
                                      & = frac{1}{6}(n+1) left[ 2(n+1)^2 - 3n - 2right] \
                                      & = frac{1}{6}(n+1)(2n^2 +n) \
                                      & = frac{1}{6}n(n+1)(2n+1)
                                      end{align}$$







                                      share|cite|improve this answer














                                      share|cite|improve this answer



                                      share|cite|improve this answer








                                      edited Jun 28 '11 at 9:25

























                                      answered Jun 27 '11 at 23:48









                                      Chris TaylorChris Taylor

                                      21.9k363108




                                      21.9k363108








                                      • 4




                                        $begingroup$
                                        The appeal of this proof is that it's sort of the discrete counterpart to the integral: $int_0^n x^2 dx= n^3/3$
                                        $endgroup$
                                        – leonbloy
                                        Jan 14 '13 at 19:35














                                      • 4




                                        $begingroup$
                                        The appeal of this proof is that it's sort of the discrete counterpart to the integral: $int_0^n x^2 dx= n^3/3$
                                        $endgroup$
                                        – leonbloy
                                        Jan 14 '13 at 19:35








                                      4




                                      4




                                      $begingroup$
                                      The appeal of this proof is that it's sort of the discrete counterpart to the integral: $int_0^n x^2 dx= n^3/3$
                                      $endgroup$
                                      – leonbloy
                                      Jan 14 '13 at 19:35




                                      $begingroup$
                                      The appeal of this proof is that it's sort of the discrete counterpart to the integral: $int_0^n x^2 dx= n^3/3$
                                      $endgroup$
                                      – leonbloy
                                      Jan 14 '13 at 19:35











                                      18












                                      $begingroup$

                                      Proof (by induction)



                                      Basis: Check it for n = 1 (it works out).



                                      Induction: Assume the result is true for a given value of $n$. That is, assume
                                      $$
                                      sum_{k = 1}^n k^2 = frac{n(n+1)(2n+1)}{6}.
                                      $$
                                      Try to show that the result holds for $n+1$.
                                      $$
                                      begin{align*}
                                      sum_{k = 1}^{n+1} k^2 &= (n+1)^2 + sum_{k=1}^n k^2\
                                      &= (n+1)^2 + frac{n(n+1)(2n+1)}{6}\
                                      &= frac{6(n+1)^2 + n(n+1)(2n+1)}{6}\
                                      &= frac{(n+1)(n+1+1)(2(n+1)+1)}{6}.
                                      end{align*}
                                      $$






                                      share|cite|improve this answer











                                      $endgroup$


















                                        18












                                        $begingroup$

                                        Proof (by induction)



                                        Basis: Check it for n = 1 (it works out).



                                        Induction: Assume the result is true for a given value of $n$. That is, assume
                                        $$
                                        sum_{k = 1}^n k^2 = frac{n(n+1)(2n+1)}{6}.
                                        $$
                                        Try to show that the result holds for $n+1$.
                                        $$
                                        begin{align*}
                                        sum_{k = 1}^{n+1} k^2 &= (n+1)^2 + sum_{k=1}^n k^2\
                                        &= (n+1)^2 + frac{n(n+1)(2n+1)}{6}\
                                        &= frac{6(n+1)^2 + n(n+1)(2n+1)}{6}\
                                        &= frac{(n+1)(n+1+1)(2(n+1)+1)}{6}.
                                        end{align*}
                                        $$






                                        share|cite|improve this answer











                                        $endgroup$
















                                          18












                                          18








                                          18





                                          $begingroup$

                                          Proof (by induction)



                                          Basis: Check it for n = 1 (it works out).



                                          Induction: Assume the result is true for a given value of $n$. That is, assume
                                          $$
                                          sum_{k = 1}^n k^2 = frac{n(n+1)(2n+1)}{6}.
                                          $$
                                          Try to show that the result holds for $n+1$.
                                          $$
                                          begin{align*}
                                          sum_{k = 1}^{n+1} k^2 &= (n+1)^2 + sum_{k=1}^n k^2\
                                          &= (n+1)^2 + frac{n(n+1)(2n+1)}{6}\
                                          &= frac{6(n+1)^2 + n(n+1)(2n+1)}{6}\
                                          &= frac{(n+1)(n+1+1)(2(n+1)+1)}{6}.
                                          end{align*}
                                          $$






                                          share|cite|improve this answer











                                          $endgroup$



                                          Proof (by induction)



                                          Basis: Check it for n = 1 (it works out).



                                          Induction: Assume the result is true for a given value of $n$. That is, assume
                                          $$
                                          sum_{k = 1}^n k^2 = frac{n(n+1)(2n+1)}{6}.
                                          $$
                                          Try to show that the result holds for $n+1$.
                                          $$
                                          begin{align*}
                                          sum_{k = 1}^{n+1} k^2 &= (n+1)^2 + sum_{k=1}^n k^2\
                                          &= (n+1)^2 + frac{n(n+1)(2n+1)}{6}\
                                          &= frac{6(n+1)^2 + n(n+1)(2n+1)}{6}\
                                          &= frac{(n+1)(n+1+1)(2(n+1)+1)}{6}.
                                          end{align*}
                                          $$







                                          share|cite|improve this answer














                                          share|cite|improve this answer



                                          share|cite|improve this answer








                                          edited Dec 3 '17 at 0:52

























                                          answered Jun 27 '11 at 23:16









                                          Austin MohrAustin Mohr

                                          20.1k35098




                                          20.1k35098























                                              16












                                              $begingroup$

                                              To verify the identity, note $rm:sum_{k=1}^n: k^2 = f(n) iff f(n+1) - f(n) = (n+1)^2:$ and $rm: f(1) = 1:. $ But it's rote polynomial arithmetic to check that the RHS polynomial satisfies this recurrence.



                                              To discover the identity, notice that any polynomial solution of the above recurrence has degree at most $3$. Hence it's easy to find the polynomial solution by substituting a cubic polynomial with undetermined coefficients.



                                              Generally one can give a formula for sums of power using Bernoulli polynomials (motivated by discrete analogs of integrals of powers). The general theory becomes much clearer when one studies finite difference calculus and umbral calculus.






                                              share|cite|improve this answer











                                              $endgroup$


















                                                16












                                                $begingroup$

                                                To verify the identity, note $rm:sum_{k=1}^n: k^2 = f(n) iff f(n+1) - f(n) = (n+1)^2:$ and $rm: f(1) = 1:. $ But it's rote polynomial arithmetic to check that the RHS polynomial satisfies this recurrence.



                                                To discover the identity, notice that any polynomial solution of the above recurrence has degree at most $3$. Hence it's easy to find the polynomial solution by substituting a cubic polynomial with undetermined coefficients.



                                                Generally one can give a formula for sums of power using Bernoulli polynomials (motivated by discrete analogs of integrals of powers). The general theory becomes much clearer when one studies finite difference calculus and umbral calculus.






                                                share|cite|improve this answer











                                                $endgroup$
















                                                  16












                                                  16








                                                  16





                                                  $begingroup$

                                                  To verify the identity, note $rm:sum_{k=1}^n: k^2 = f(n) iff f(n+1) - f(n) = (n+1)^2:$ and $rm: f(1) = 1:. $ But it's rote polynomial arithmetic to check that the RHS polynomial satisfies this recurrence.



                                                  To discover the identity, notice that any polynomial solution of the above recurrence has degree at most $3$. Hence it's easy to find the polynomial solution by substituting a cubic polynomial with undetermined coefficients.



                                                  Generally one can give a formula for sums of power using Bernoulli polynomials (motivated by discrete analogs of integrals of powers). The general theory becomes much clearer when one studies finite difference calculus and umbral calculus.






                                                  share|cite|improve this answer











                                                  $endgroup$



                                                  To verify the identity, note $rm:sum_{k=1}^n: k^2 = f(n) iff f(n+1) - f(n) = (n+1)^2:$ and $rm: f(1) = 1:. $ But it's rote polynomial arithmetic to check that the RHS polynomial satisfies this recurrence.



                                                  To discover the identity, notice that any polynomial solution of the above recurrence has degree at most $3$. Hence it's easy to find the polynomial solution by substituting a cubic polynomial with undetermined coefficients.



                                                  Generally one can give a formula for sums of power using Bernoulli polynomials (motivated by discrete analogs of integrals of powers). The general theory becomes much clearer when one studies finite difference calculus and umbral calculus.







                                                  share|cite|improve this answer














                                                  share|cite|improve this answer



                                                  share|cite|improve this answer








                                                  edited Apr 13 '17 at 12:21









                                                  Community

                                                  1




                                                  1










                                                  answered Jun 27 '11 at 23:55









                                                  Bill DubuqueBill Dubuque

                                                  209k29191633




                                                  209k29191633























                                                      14












                                                      $begingroup$

                                                      I think it's useful to report here another proof that I have posted on Mathoverflow.



                                                      Write down numbers in an equilateral triangle as follows:



                                                          1
                                                      2 2
                                                      3 3 3
                                                      4 4 4 4


                                                      Now, clearly the sum of the numbers in the triangle is $Q_n:=1^2+2^2+dots+n^2$. On the other hand, if you superimpose three such triangles rotated by $120^circ$ each, like these ones



                                                          1          4          4 
                                                      2 2 3 4 4 3
                                                      3 3 3 2 3 4 4 3 2
                                                      4 4 4 4 1 2 3 4 4 3 2 1


                                                      then the sum of the numbers in each position equals $2n+1$. Therefore, you can double-count $3Q_n=frac{n(n+1)}{2}(2n+1)$. $square$



                                                      The proof is not mine and I do not claim otherwise. I first heard it from János Pataki. It is similar (but simpler) to the proof appearing on Wikipedia as I am writing this.



                                                      How to prove formally that all positions sum to $2n+1$? Easy induction: moving down-left or down-right from the topmost number does not alter the sum, since one of the three summand increases and one decreases. This is a discrete analogue of the Euclidean geometry theorem "given a point $P$ in an equilateral triangle $ABC$, the sum of its three distances from the sides is constant" (proof: sum the areas of $APB,BPC,CPA$), which you can mention as well.






                                                      share|cite|improve this answer











                                                      $endgroup$













                                                      • $begingroup$
                                                        Nice, though I think the proof by Man-Keung Siu mentioned above is related.
                                                        $endgroup$
                                                        – ShreevatsaR
                                                        Mar 19 '14 at 16:39
















                                                      14












                                                      $begingroup$

                                                      I think it's useful to report here another proof that I have posted on Mathoverflow.



                                                      Write down numbers in an equilateral triangle as follows:



                                                          1
                                                      2 2
                                                      3 3 3
                                                      4 4 4 4


                                                      Now, clearly the sum of the numbers in the triangle is $Q_n:=1^2+2^2+dots+n^2$. On the other hand, if you superimpose three such triangles rotated by $120^circ$ each, like these ones



                                                          1          4          4 
                                                      2 2 3 4 4 3
                                                      3 3 3 2 3 4 4 3 2
                                                      4 4 4 4 1 2 3 4 4 3 2 1


                                                      then the sum of the numbers in each position equals $2n+1$. Therefore, you can double-count $3Q_n=frac{n(n+1)}{2}(2n+1)$. $square$



                                                      The proof is not mine and I do not claim otherwise. I first heard it from János Pataki. It is similar (but simpler) to the proof appearing on Wikipedia as I am writing this.



                                                      How to prove formally that all positions sum to $2n+1$? Easy induction: moving down-left or down-right from the topmost number does not alter the sum, since one of the three summand increases and one decreases. This is a discrete analogue of the Euclidean geometry theorem "given a point $P$ in an equilateral triangle $ABC$, the sum of its three distances from the sides is constant" (proof: sum the areas of $APB,BPC,CPA$), which you can mention as well.






                                                      share|cite|improve this answer











                                                      $endgroup$













                                                      • $begingroup$
                                                        Nice, though I think the proof by Man-Keung Siu mentioned above is related.
                                                        $endgroup$
                                                        – ShreevatsaR
                                                        Mar 19 '14 at 16:39














                                                      14












                                                      14








                                                      14





                                                      $begingroup$

                                                      I think it's useful to report here another proof that I have posted on Mathoverflow.



                                                      Write down numbers in an equilateral triangle as follows:



                                                          1
                                                      2 2
                                                      3 3 3
                                                      4 4 4 4


                                                      Now, clearly the sum of the numbers in the triangle is $Q_n:=1^2+2^2+dots+n^2$. On the other hand, if you superimpose three such triangles rotated by $120^circ$ each, like these ones



                                                          1          4          4 
                                                      2 2 3 4 4 3
                                                      3 3 3 2 3 4 4 3 2
                                                      4 4 4 4 1 2 3 4 4 3 2 1


                                                      then the sum of the numbers in each position equals $2n+1$. Therefore, you can double-count $3Q_n=frac{n(n+1)}{2}(2n+1)$. $square$



                                                      The proof is not mine and I do not claim otherwise. I first heard it from János Pataki. It is similar (but simpler) to the proof appearing on Wikipedia as I am writing this.



                                                      How to prove formally that all positions sum to $2n+1$? Easy induction: moving down-left or down-right from the topmost number does not alter the sum, since one of the three summand increases and one decreases. This is a discrete analogue of the Euclidean geometry theorem "given a point $P$ in an equilateral triangle $ABC$, the sum of its three distances from the sides is constant" (proof: sum the areas of $APB,BPC,CPA$), which you can mention as well.






                                                      share|cite|improve this answer











                                                      $endgroup$



                                                      I think it's useful to report here another proof that I have posted on Mathoverflow.



                                                      Write down numbers in an equilateral triangle as follows:



                                                          1
                                                      2 2
                                                      3 3 3
                                                      4 4 4 4


                                                      Now, clearly the sum of the numbers in the triangle is $Q_n:=1^2+2^2+dots+n^2$. On the other hand, if you superimpose three such triangles rotated by $120^circ$ each, like these ones



                                                          1          4          4 
                                                      2 2 3 4 4 3
                                                      3 3 3 2 3 4 4 3 2
                                                      4 4 4 4 1 2 3 4 4 3 2 1


                                                      then the sum of the numbers in each position equals $2n+1$. Therefore, you can double-count $3Q_n=frac{n(n+1)}{2}(2n+1)$. $square$



                                                      The proof is not mine and I do not claim otherwise. I first heard it from János Pataki. It is similar (but simpler) to the proof appearing on Wikipedia as I am writing this.



                                                      How to prove formally that all positions sum to $2n+1$? Easy induction: moving down-left or down-right from the topmost number does not alter the sum, since one of the three summand increases and one decreases. This is a discrete analogue of the Euclidean geometry theorem "given a point $P$ in an equilateral triangle $ABC$, the sum of its three distances from the sides is constant" (proof: sum the areas of $APB,BPC,CPA$), which you can mention as well.







                                                      share|cite|improve this answer














                                                      share|cite|improve this answer



                                                      share|cite|improve this answer








                                                      edited Apr 13 '17 at 12:58









                                                      Community

                                                      1




                                                      1










                                                      answered Mar 19 '14 at 16:08









                                                      Federico PoloniFederico Poloni

                                                      2,4801327




                                                      2,4801327












                                                      • $begingroup$
                                                        Nice, though I think the proof by Man-Keung Siu mentioned above is related.
                                                        $endgroup$
                                                        – ShreevatsaR
                                                        Mar 19 '14 at 16:39


















                                                      • $begingroup$
                                                        Nice, though I think the proof by Man-Keung Siu mentioned above is related.
                                                        $endgroup$
                                                        – ShreevatsaR
                                                        Mar 19 '14 at 16:39
















                                                      $begingroup$
                                                      Nice, though I think the proof by Man-Keung Siu mentioned above is related.
                                                      $endgroup$
                                                      – ShreevatsaR
                                                      Mar 19 '14 at 16:39




                                                      $begingroup$
                                                      Nice, though I think the proof by Man-Keung Siu mentioned above is related.
                                                      $endgroup$
                                                      – ShreevatsaR
                                                      Mar 19 '14 at 16:39











                                                      12












                                                      $begingroup$

                                                      Sums of polynomials can be done completely mechanically (no insight required, just turn the handle!) using the discrete calculus. Bill Dubuque mentions this in his answer, but I think it's nice to see a worked example.



                                                      Represent $k^2$ in terms of falling powers (easy by inspection in this case, but you can use Stirling subset numbers to convert): $$ k^2 = k^{underline 2} + k^{underline 1}$$



                                                      Sums of falling powers are easy, just like integration of ordinary powers, except for the treatment of limits: $$ sum_{k=1}^n k^{underline 2} + k^{underline 1} = bigg({1over 3}k^{underline 3} + {1over 2}k^{underline 2}bigg) bigg|^{n+1}_0$$



                                                      And then convert back into ordinary powers (by expansion, or using signed Stirling cycle numbers): $$ {1over 3}((n+1)^3 - 3(n+1)^2 + 2(n+1)) + {1over 2}((n+1)^2 - (n+1))$$



                                                      And then you can rearrange to get the answer you want.






                                                      share|cite|improve this answer











                                                      $endgroup$


















                                                        12












                                                        $begingroup$

                                                        Sums of polynomials can be done completely mechanically (no insight required, just turn the handle!) using the discrete calculus. Bill Dubuque mentions this in his answer, but I think it's nice to see a worked example.



                                                        Represent $k^2$ in terms of falling powers (easy by inspection in this case, but you can use Stirling subset numbers to convert): $$ k^2 = k^{underline 2} + k^{underline 1}$$



                                                        Sums of falling powers are easy, just like integration of ordinary powers, except for the treatment of limits: $$ sum_{k=1}^n k^{underline 2} + k^{underline 1} = bigg({1over 3}k^{underline 3} + {1over 2}k^{underline 2}bigg) bigg|^{n+1}_0$$



                                                        And then convert back into ordinary powers (by expansion, or using signed Stirling cycle numbers): $$ {1over 3}((n+1)^3 - 3(n+1)^2 + 2(n+1)) + {1over 2}((n+1)^2 - (n+1))$$



                                                        And then you can rearrange to get the answer you want.






                                                        share|cite|improve this answer











                                                        $endgroup$
















                                                          12












                                                          12








                                                          12





                                                          $begingroup$

                                                          Sums of polynomials can be done completely mechanically (no insight required, just turn the handle!) using the discrete calculus. Bill Dubuque mentions this in his answer, but I think it's nice to see a worked example.



                                                          Represent $k^2$ in terms of falling powers (easy by inspection in this case, but you can use Stirling subset numbers to convert): $$ k^2 = k^{underline 2} + k^{underline 1}$$



                                                          Sums of falling powers are easy, just like integration of ordinary powers, except for the treatment of limits: $$ sum_{k=1}^n k^{underline 2} + k^{underline 1} = bigg({1over 3}k^{underline 3} + {1over 2}k^{underline 2}bigg) bigg|^{n+1}_0$$



                                                          And then convert back into ordinary powers (by expansion, or using signed Stirling cycle numbers): $$ {1over 3}((n+1)^3 - 3(n+1)^2 + 2(n+1)) + {1over 2}((n+1)^2 - (n+1))$$



                                                          And then you can rearrange to get the answer you want.






                                                          share|cite|improve this answer











                                                          $endgroup$



                                                          Sums of polynomials can be done completely mechanically (no insight required, just turn the handle!) using the discrete calculus. Bill Dubuque mentions this in his answer, but I think it's nice to see a worked example.



                                                          Represent $k^2$ in terms of falling powers (easy by inspection in this case, but you can use Stirling subset numbers to convert): $$ k^2 = k^{underline 2} + k^{underline 1}$$



                                                          Sums of falling powers are easy, just like integration of ordinary powers, except for the treatment of limits: $$ sum_{k=1}^n k^{underline 2} + k^{underline 1} = bigg({1over 3}k^{underline 3} + {1over 2}k^{underline 2}bigg) bigg|^{n+1}_0$$



                                                          And then convert back into ordinary powers (by expansion, or using signed Stirling cycle numbers): $$ {1over 3}((n+1)^3 - 3(n+1)^2 + 2(n+1)) + {1over 2}((n+1)^2 - (n+1))$$



                                                          And then you can rearrange to get the answer you want.







                                                          share|cite|improve this answer














                                                          share|cite|improve this answer



                                                          share|cite|improve this answer








                                                          edited Jul 10 '11 at 23:20

























                                                          answered Jul 10 '11 at 14:12









                                                          Gareth ReesGareth Rees

                                                          57129




                                                          57129























                                                              12












                                                              $begingroup$

                                                              A probabilistic method that I learned from Jim Pitman's book Probability (exercise 3.3.10) is as follows. Let $X$ be uniformly distributed on the set ${ 1, 2, ldots, n }$. Then
                                                              $$ E(X^3) = (1^3 + 2^3 + ldots + n^3)/n $$
                                                              and
                                                              $$ E((X+1)^3) = (2^3 + 3^3 + ldots +(n+1)^3)/n. $$
                                                              Subtracting the first of these from the second we get
                                                              $$ E((X+1)^3 - X^3) = ((n+1)^3 - 1)/n $$
                                                              and we can simplify both sides a bit to get
                                                              $$ E(3X^2 + 3X + 1) = n^2 + 3n + 3.$$
                                                              By linearity of expectation we can expand the left-hand side to get
                                                              $$ 3 E(X^2) + 3 E(X) + 1 = n^2 + 3n + 3. $$



                                                              Now $E(X) = (1+2+ldots+n)/n = (n+1)/2$. Substituting this in and solving for $E(X^2)$ gives



                                                              $$ E(X^2) = {(n+1)(2n+1) over 6} $$
                                                              but of course $E(X^2) = (1^2+2^2+cdots +n^2)/n$.



                                                              Similarly, we can derive for each $k$
                                                              $$ sum_{j=0}^{k-1} {k choose j} E(X^j) = sum_{l=1}^k {k choose l} n^{l-1} $$
                                                              and so if we know $E(X^0), ldots, E(X^{k-2})$ we can solve for $E(X^{k-1})$. So this method generalizes to higher moments as well.






                                                              share|cite|improve this answer









                                                              $endgroup$













                                                              • $begingroup$
                                                                never seen such a demonstration like this, thanks!!!
                                                                $endgroup$
                                                                – jonaprieto
                                                                Apr 25 '12 at 6:11










                                                              • $begingroup$
                                                                I was rather surprised when I saw this for the first time as well.
                                                                $endgroup$
                                                                – Michael Lugo
                                                                Apr 25 '12 at 16:32






                                                              • 1




                                                                $begingroup$
                                                                Nice, needs more up votes.
                                                                $endgroup$
                                                                – k.stm
                                                                May 28 '13 at 7:13
















                                                              12












                                                              $begingroup$

                                                              A probabilistic method that I learned from Jim Pitman's book Probability (exercise 3.3.10) is as follows. Let $X$ be uniformly distributed on the set ${ 1, 2, ldots, n }$. Then
                                                              $$ E(X^3) = (1^3 + 2^3 + ldots + n^3)/n $$
                                                              and
                                                              $$ E((X+1)^3) = (2^3 + 3^3 + ldots +(n+1)^3)/n. $$
                                                              Subtracting the first of these from the second we get
                                                              $$ E((X+1)^3 - X^3) = ((n+1)^3 - 1)/n $$
                                                              and we can simplify both sides a bit to get
                                                              $$ E(3X^2 + 3X + 1) = n^2 + 3n + 3.$$
                                                              By linearity of expectation we can expand the left-hand side to get
                                                              $$ 3 E(X^2) + 3 E(X) + 1 = n^2 + 3n + 3. $$



                                                              Now $E(X) = (1+2+ldots+n)/n = (n+1)/2$. Substituting this in and solving for $E(X^2)$ gives



                                                              $$ E(X^2) = {(n+1)(2n+1) over 6} $$
                                                              but of course $E(X^2) = (1^2+2^2+cdots +n^2)/n$.



                                                              Similarly, we can derive for each $k$
                                                              $$ sum_{j=0}^{k-1} {k choose j} E(X^j) = sum_{l=1}^k {k choose l} n^{l-1} $$
                                                              and so if we know $E(X^0), ldots, E(X^{k-2})$ we can solve for $E(X^{k-1})$. So this method generalizes to higher moments as well.






                                                              share|cite|improve this answer









                                                              $endgroup$













                                                              • $begingroup$
                                                                never seen such a demonstration like this, thanks!!!
                                                                $endgroup$
                                                                – jonaprieto
                                                                Apr 25 '12 at 6:11










                                                              • $begingroup$
                                                                I was rather surprised when I saw this for the first time as well.
                                                                $endgroup$
                                                                – Michael Lugo
                                                                Apr 25 '12 at 16:32






                                                              • 1




                                                                $begingroup$
                                                                Nice, needs more up votes.
                                                                $endgroup$
                                                                – k.stm
                                                                May 28 '13 at 7:13














                                                              12












                                                              12








                                                              12





                                                              $begingroup$

                                                              A probabilistic method that I learned from Jim Pitman's book Probability (exercise 3.3.10) is as follows. Let $X$ be uniformly distributed on the set ${ 1, 2, ldots, n }$. Then
                                                              $$ E(X^3) = (1^3 + 2^3 + ldots + n^3)/n $$
                                                              and
                                                              $$ E((X+1)^3) = (2^3 + 3^3 + ldots +(n+1)^3)/n. $$
                                                              Subtracting the first of these from the second we get
                                                              $$ E((X+1)^3 - X^3) = ((n+1)^3 - 1)/n $$
                                                              and we can simplify both sides a bit to get
                                                              $$ E(3X^2 + 3X + 1) = n^2 + 3n + 3.$$
                                                              By linearity of expectation we can expand the left-hand side to get
                                                              $$ 3 E(X^2) + 3 E(X) + 1 = n^2 + 3n + 3. $$



                                                              Now $E(X) = (1+2+ldots+n)/n = (n+1)/2$. Substituting this in and solving for $E(X^2)$ gives



                                                              $$ E(X^2) = {(n+1)(2n+1) over 6} $$
                                                              but of course $E(X^2) = (1^2+2^2+cdots +n^2)/n$.



                                                              Similarly, we can derive for each $k$
                                                              $$ sum_{j=0}^{k-1} {k choose j} E(X^j) = sum_{l=1}^k {k choose l} n^{l-1} $$
                                                              and so if we know $E(X^0), ldots, E(X^{k-2})$ we can solve for $E(X^{k-1})$. So this method generalizes to higher moments as well.






                                                              share|cite|improve this answer









                                                              $endgroup$



                                                              A probabilistic method that I learned from Jim Pitman's book Probability (exercise 3.3.10) is as follows. Let $X$ be uniformly distributed on the set ${ 1, 2, ldots, n }$. Then
                                                              $$ E(X^3) = (1^3 + 2^3 + ldots + n^3)/n $$
                                                              and
                                                              $$ E((X+1)^3) = (2^3 + 3^3 + ldots +(n+1)^3)/n. $$
                                                              Subtracting the first of these from the second we get
                                                              $$ E((X+1)^3 - X^3) = ((n+1)^3 - 1)/n $$
                                                              and we can simplify both sides a bit to get
                                                              $$ E(3X^2 + 3X + 1) = n^2 + 3n + 3.$$
                                                              By linearity of expectation we can expand the left-hand side to get
                                                              $$ 3 E(X^2) + 3 E(X) + 1 = n^2 + 3n + 3. $$



                                                              Now $E(X) = (1+2+ldots+n)/n = (n+1)/2$. Substituting this in and solving for $E(X^2)$ gives



                                                              $$ E(X^2) = {(n+1)(2n+1) over 6} $$
                                                              but of course $E(X^2) = (1^2+2^2+cdots +n^2)/n$.



                                                              Similarly, we can derive for each $k$
                                                              $$ sum_{j=0}^{k-1} {k choose j} E(X^j) = sum_{l=1}^k {k choose l} n^{l-1} $$
                                                              and so if we know $E(X^0), ldots, E(X^{k-2})$ we can solve for $E(X^{k-1})$. So this method generalizes to higher moments as well.







                                                              share|cite|improve this answer












                                                              share|cite|improve this answer



                                                              share|cite|improve this answer










                                                              answered Oct 28 '11 at 21:59









                                                              Michael LugoMichael Lugo

                                                              18k33576




                                                              18k33576












                                                              • $begingroup$
                                                                never seen such a demonstration like this, thanks!!!
                                                                $endgroup$
                                                                – jonaprieto
                                                                Apr 25 '12 at 6:11










                                                              • $begingroup$
                                                                I was rather surprised when I saw this for the first time as well.
                                                                $endgroup$
                                                                – Michael Lugo
                                                                Apr 25 '12 at 16:32






                                                              • 1




                                                                $begingroup$
                                                                Nice, needs more up votes.
                                                                $endgroup$
                                                                – k.stm
                                                                May 28 '13 at 7:13


















                                                              • $begingroup$
                                                                never seen such a demonstration like this, thanks!!!
                                                                $endgroup$
                                                                – jonaprieto
                                                                Apr 25 '12 at 6:11










                                                              • $begingroup$
                                                                I was rather surprised when I saw this for the first time as well.
                                                                $endgroup$
                                                                – Michael Lugo
                                                                Apr 25 '12 at 16:32






                                                              • 1




                                                                $begingroup$
                                                                Nice, needs more up votes.
                                                                $endgroup$
                                                                – k.stm
                                                                May 28 '13 at 7:13
















                                                              $begingroup$
                                                              never seen such a demonstration like this, thanks!!!
                                                              $endgroup$
                                                              – jonaprieto
                                                              Apr 25 '12 at 6:11




                                                              $begingroup$
                                                              never seen such a demonstration like this, thanks!!!
                                                              $endgroup$
                                                              – jonaprieto
                                                              Apr 25 '12 at 6:11












                                                              $begingroup$
                                                              I was rather surprised when I saw this for the first time as well.
                                                              $endgroup$
                                                              – Michael Lugo
                                                              Apr 25 '12 at 16:32




                                                              $begingroup$
                                                              I was rather surprised when I saw this for the first time as well.
                                                              $endgroup$
                                                              – Michael Lugo
                                                              Apr 25 '12 at 16:32




                                                              1




                                                              1




                                                              $begingroup$
                                                              Nice, needs more up votes.
                                                              $endgroup$
                                                              – k.stm
                                                              May 28 '13 at 7:13




                                                              $begingroup$
                                                              Nice, needs more up votes.
                                                              $endgroup$
                                                              – k.stm
                                                              May 28 '13 at 7:13











                                                              11












                                                              $begingroup$

                                                              This is a method that I learned from Polya's Mathematics and Plausible Reasoning: Let $s(n) = 1 + 2 + cdots + n$ and let $t(n) = 1^2 + 2^2 + cdots + n^2$. Make a small table as follows:



                                                                 n = 1 2  3  4  5
                                                              t(n) = 1 5 14 30 55
                                                              s(n) = 1 3 6 10 15


                                                              Note the ratio $r(n) = t(n)/s(n)$ for sucessive values of $n$:



                                                              R(1) = 1 = 3/3
                                                              R(2) = 5/3
                                                              R(3) = 14/6 = 7/3
                                                              R(4) = 30/10 = 3 = 9/3
                                                              R(5) = 55/15 = 11/3


                                                              Based on the pattern it seems that $r(n) = (2n+1)/3$ (and in fact it is: just prove it by induction). It follows that $t(n) = r(n)s(n)$. Now use the fact that $s(n) = n(n+1)/2$.






                                                              share|cite|improve this answer









                                                              $endgroup$


















                                                                11












                                                                $begingroup$

                                                                This is a method that I learned from Polya's Mathematics and Plausible Reasoning: Let $s(n) = 1 + 2 + cdots + n$ and let $t(n) = 1^2 + 2^2 + cdots + n^2$. Make a small table as follows:



                                                                   n = 1 2  3  4  5
                                                                t(n) = 1 5 14 30 55
                                                                s(n) = 1 3 6 10 15


                                                                Note the ratio $r(n) = t(n)/s(n)$ for sucessive values of $n$:



                                                                R(1) = 1 = 3/3
                                                                R(2) = 5/3
                                                                R(3) = 14/6 = 7/3
                                                                R(4) = 30/10 = 3 = 9/3
                                                                R(5) = 55/15 = 11/3


                                                                Based on the pattern it seems that $r(n) = (2n+1)/3$ (and in fact it is: just prove it by induction). It follows that $t(n) = r(n)s(n)$. Now use the fact that $s(n) = n(n+1)/2$.






                                                                share|cite|improve this answer









                                                                $endgroup$
















                                                                  11












                                                                  11








                                                                  11





                                                                  $begingroup$

                                                                  This is a method that I learned from Polya's Mathematics and Plausible Reasoning: Let $s(n) = 1 + 2 + cdots + n$ and let $t(n) = 1^2 + 2^2 + cdots + n^2$. Make a small table as follows:



                                                                     n = 1 2  3  4  5
                                                                  t(n) = 1 5 14 30 55
                                                                  s(n) = 1 3 6 10 15


                                                                  Note the ratio $r(n) = t(n)/s(n)$ for sucessive values of $n$:



                                                                  R(1) = 1 = 3/3
                                                                  R(2) = 5/3
                                                                  R(3) = 14/6 = 7/3
                                                                  R(4) = 30/10 = 3 = 9/3
                                                                  R(5) = 55/15 = 11/3


                                                                  Based on the pattern it seems that $r(n) = (2n+1)/3$ (and in fact it is: just prove it by induction). It follows that $t(n) = r(n)s(n)$. Now use the fact that $s(n) = n(n+1)/2$.






                                                                  share|cite|improve this answer









                                                                  $endgroup$



                                                                  This is a method that I learned from Polya's Mathematics and Plausible Reasoning: Let $s(n) = 1 + 2 + cdots + n$ and let $t(n) = 1^2 + 2^2 + cdots + n^2$. Make a small table as follows:



                                                                     n = 1 2  3  4  5
                                                                  t(n) = 1 5 14 30 55
                                                                  s(n) = 1 3 6 10 15


                                                                  Note the ratio $r(n) = t(n)/s(n)$ for sucessive values of $n$:



                                                                  R(1) = 1 = 3/3
                                                                  R(2) = 5/3
                                                                  R(3) = 14/6 = 7/3
                                                                  R(4) = 30/10 = 3 = 9/3
                                                                  R(5) = 55/15 = 11/3


                                                                  Based on the pattern it seems that $r(n) = (2n+1)/3$ (and in fact it is: just prove it by induction). It follows that $t(n) = r(n)s(n)$. Now use the fact that $s(n) = n(n+1)/2$.







                                                                  share|cite|improve this answer












                                                                  share|cite|improve this answer



                                                                  share|cite|improve this answer










                                                                  answered Jul 11 '11 at 1:00









                                                                  echooneechoone

                                                                  1,020725




                                                                  1,020725























                                                                      9












                                                                      $begingroup$

                                                                      A natural approach for this kind of problems when you don't know the result is to proceed as follows :



                                                                      We may want to write the sum $sum_{k=1}^n k^2$ as a telescopic sum, so we will try to find a polynomial of degree 3 ( why ? ) $P$ so that $Pleft( k+1 right) - Pleft(kright)=k^2$. Let $Pleft( x right) = ax^3+bx^2+cx$ for all reals $x$, then our constraint becomes :



                                                                      $k^2= aleft( left(k+1right)^3 - k^3 right) + bleft( left(k+1right)^2 - k^2 right) + c$



                                                                      Which after expanding and rearranging becomes :



                                                                      $k^2 = 3ak^2 + left( 3a+2b right)k + a+b+c$



                                                                      But we know that two polynomials are equal iff their coefficients are equal too, so we just need to solve this system :



                                                                      $left{ begin{aligned}
                                                                      a &= frac{1}{3} \
                                                                      3a+2b &= 0 \
                                                                      a+b+c &= 0
                                                                      end{aligned} right.$



                                                                      Which gives us $left( a,b,c right) = left( frac{1}{3}, frac{-1}{2}, frac{1}{6} right)$



                                                                      And Voilà, we just found the coefficients of our polynomial ! Now we just have to evaluate our telescopic sum :



                                                                      $sum_{k=1}^n k^2 = sum_{k=1}^n Pleft( k+1 right) - Pleft(kright) = Pleft(n+1right)-underbrace{Pleft(1right)}_{=0}$



                                                                      $sum_{k=1}^n k^2 = frac{1}{3}left(n+1right)^3 - frac{1}{2}left(n+1right)^2+frac{1}{6}left(n+1right)$



                                                                      $sum_{k=1}^n k^2 = frac{1}{6}left(n+1right)left( 2 left(n+1right)^2 - 3 left(n+1 right) + 1 right)$



                                                                      $sum_{k=1}^n k^2 = frac{1}{6}left(n+1right)left( 2n^2+n right)$



                                                                      $sum_{k=1}^n k^2 = frac{1}{6}nleft(n+1right)left(2n+1right)$



                                                                      Which completes the proof :-)






                                                                      share|cite|improve this answer









                                                                      $endgroup$


















                                                                        9












                                                                        $begingroup$

                                                                        A natural approach for this kind of problems when you don't know the result is to proceed as follows :



                                                                        We may want to write the sum $sum_{k=1}^n k^2$ as a telescopic sum, so we will try to find a polynomial of degree 3 ( why ? ) $P$ so that $Pleft( k+1 right) - Pleft(kright)=k^2$. Let $Pleft( x right) = ax^3+bx^2+cx$ for all reals $x$, then our constraint becomes :



                                                                        $k^2= aleft( left(k+1right)^3 - k^3 right) + bleft( left(k+1right)^2 - k^2 right) + c$



                                                                        Which after expanding and rearranging becomes :



                                                                        $k^2 = 3ak^2 + left( 3a+2b right)k + a+b+c$



                                                                        But we know that two polynomials are equal iff their coefficients are equal too, so we just need to solve this system :



                                                                        $left{ begin{aligned}
                                                                        a &= frac{1}{3} \
                                                                        3a+2b &= 0 \
                                                                        a+b+c &= 0
                                                                        end{aligned} right.$



                                                                        Which gives us $left( a,b,c right) = left( frac{1}{3}, frac{-1}{2}, frac{1}{6} right)$



                                                                        And Voilà, we just found the coefficients of our polynomial ! Now we just have to evaluate our telescopic sum :



                                                                        $sum_{k=1}^n k^2 = sum_{k=1}^n Pleft( k+1 right) - Pleft(kright) = Pleft(n+1right)-underbrace{Pleft(1right)}_{=0}$



                                                                        $sum_{k=1}^n k^2 = frac{1}{3}left(n+1right)^3 - frac{1}{2}left(n+1right)^2+frac{1}{6}left(n+1right)$



                                                                        $sum_{k=1}^n k^2 = frac{1}{6}left(n+1right)left( 2 left(n+1right)^2 - 3 left(n+1 right) + 1 right)$



                                                                        $sum_{k=1}^n k^2 = frac{1}{6}left(n+1right)left( 2n^2+n right)$



                                                                        $sum_{k=1}^n k^2 = frac{1}{6}nleft(n+1right)left(2n+1right)$



                                                                        Which completes the proof :-)






                                                                        share|cite|improve this answer









                                                                        $endgroup$
















                                                                          9












                                                                          9








                                                                          9





                                                                          $begingroup$

                                                                          A natural approach for this kind of problems when you don't know the result is to proceed as follows :



                                                                          We may want to write the sum $sum_{k=1}^n k^2$ as a telescopic sum, so we will try to find a polynomial of degree 3 ( why ? ) $P$ so that $Pleft( k+1 right) - Pleft(kright)=k^2$. Let $Pleft( x right) = ax^3+bx^2+cx$ for all reals $x$, then our constraint becomes :



                                                                          $k^2= aleft( left(k+1right)^3 - k^3 right) + bleft( left(k+1right)^2 - k^2 right) + c$



                                                                          Which after expanding and rearranging becomes :



                                                                          $k^2 = 3ak^2 + left( 3a+2b right)k + a+b+c$



                                                                          But we know that two polynomials are equal iff their coefficients are equal too, so we just need to solve this system :



                                                                          $left{ begin{aligned}
                                                                          a &= frac{1}{3} \
                                                                          3a+2b &= 0 \
                                                                          a+b+c &= 0
                                                                          end{aligned} right.$



                                                                          Which gives us $left( a,b,c right) = left( frac{1}{3}, frac{-1}{2}, frac{1}{6} right)$



                                                                          And Voilà, we just found the coefficients of our polynomial ! Now we just have to evaluate our telescopic sum :



                                                                          $sum_{k=1}^n k^2 = sum_{k=1}^n Pleft( k+1 right) - Pleft(kright) = Pleft(n+1right)-underbrace{Pleft(1right)}_{=0}$



                                                                          $sum_{k=1}^n k^2 = frac{1}{3}left(n+1right)^3 - frac{1}{2}left(n+1right)^2+frac{1}{6}left(n+1right)$



                                                                          $sum_{k=1}^n k^2 = frac{1}{6}left(n+1right)left( 2 left(n+1right)^2 - 3 left(n+1 right) + 1 right)$



                                                                          $sum_{k=1}^n k^2 = frac{1}{6}left(n+1right)left( 2n^2+n right)$



                                                                          $sum_{k=1}^n k^2 = frac{1}{6}nleft(n+1right)left(2n+1right)$



                                                                          Which completes the proof :-)






                                                                          share|cite|improve this answer









                                                                          $endgroup$



                                                                          A natural approach for this kind of problems when you don't know the result is to proceed as follows :



                                                                          We may want to write the sum $sum_{k=1}^n k^2$ as a telescopic sum, so we will try to find a polynomial of degree 3 ( why ? ) $P$ so that $Pleft( k+1 right) - Pleft(kright)=k^2$. Let $Pleft( x right) = ax^3+bx^2+cx$ for all reals $x$, then our constraint becomes :



                                                                          $k^2= aleft( left(k+1right)^3 - k^3 right) + bleft( left(k+1right)^2 - k^2 right) + c$



                                                                          Which after expanding and rearranging becomes :



                                                                          $k^2 = 3ak^2 + left( 3a+2b right)k + a+b+c$



                                                                          But we know that two polynomials are equal iff their coefficients are equal too, so we just need to solve this system :



                                                                          $left{ begin{aligned}
                                                                          a &= frac{1}{3} \
                                                                          3a+2b &= 0 \
                                                                          a+b+c &= 0
                                                                          end{aligned} right.$



                                                                          Which gives us $left( a,b,c right) = left( frac{1}{3}, frac{-1}{2}, frac{1}{6} right)$



                                                                          And Voilà, we just found the coefficients of our polynomial ! Now we just have to evaluate our telescopic sum :



                                                                          $sum_{k=1}^n k^2 = sum_{k=1}^n Pleft( k+1 right) - Pleft(kright) = Pleft(n+1right)-underbrace{Pleft(1right)}_{=0}$



                                                                          $sum_{k=1}^n k^2 = frac{1}{3}left(n+1right)^3 - frac{1}{2}left(n+1right)^2+frac{1}{6}left(n+1right)$



                                                                          $sum_{k=1}^n k^2 = frac{1}{6}left(n+1right)left( 2 left(n+1right)^2 - 3 left(n+1 right) + 1 right)$



                                                                          $sum_{k=1}^n k^2 = frac{1}{6}left(n+1right)left( 2n^2+n right)$



                                                                          $sum_{k=1}^n k^2 = frac{1}{6}nleft(n+1right)left(2n+1right)$



                                                                          Which completes the proof :-)







                                                                          share|cite|improve this answer












                                                                          share|cite|improve this answer



                                                                          share|cite|improve this answer










                                                                          answered Jul 10 '11 at 12:41









                                                                          BS.BS.

                                                                          250111




                                                                          250111























                                                                              8












                                                                              $begingroup$

                                                                              The standard method is induction and you should look it up as it is a popular second example (first is $sum n$)



                                                                              Another argument is use: $$24n^2 +2= (2n+1)^3-(2n-1)^3$$ and get a telescoping sum.



                                                                              i.e $$24sum_1^n k^2 +2n = sum_1^n (2k+1)^3-sum_1^n (2k-1)^3$$ $$24sum_1^n k^2 +2n = (2n+1)^3-1$$
                                                                              $$24sum_1^n k^2 =8 n^3+12 n^2+4 n$$ $$24sum_1^n k^2 =4 n (n+1) (2 n+1)$$ $$sum_1^n k^2 = frac{n (n+1) (2 n+1)}{6}$$






                                                                              share|cite|improve this answer











                                                                              $endgroup$









                                                                              • 1




                                                                                $begingroup$
                                                                                For a combinatorial argument see Sivaram's answer here
                                                                                $endgroup$
                                                                                – kuch nahi
                                                                                Jun 27 '11 at 23:23
















                                                                              8












                                                                              $begingroup$

                                                                              The standard method is induction and you should look it up as it is a popular second example (first is $sum n$)



                                                                              Another argument is use: $$24n^2 +2= (2n+1)^3-(2n-1)^3$$ and get a telescoping sum.



                                                                              i.e $$24sum_1^n k^2 +2n = sum_1^n (2k+1)^3-sum_1^n (2k-1)^3$$ $$24sum_1^n k^2 +2n = (2n+1)^3-1$$
                                                                              $$24sum_1^n k^2 =8 n^3+12 n^2+4 n$$ $$24sum_1^n k^2 =4 n (n+1) (2 n+1)$$ $$sum_1^n k^2 = frac{n (n+1) (2 n+1)}{6}$$






                                                                              share|cite|improve this answer











                                                                              $endgroup$









                                                                              • 1




                                                                                $begingroup$
                                                                                For a combinatorial argument see Sivaram's answer here
                                                                                $endgroup$
                                                                                – kuch nahi
                                                                                Jun 27 '11 at 23:23














                                                                              8












                                                                              8








                                                                              8





                                                                              $begingroup$

                                                                              The standard method is induction and you should look it up as it is a popular second example (first is $sum n$)



                                                                              Another argument is use: $$24n^2 +2= (2n+1)^3-(2n-1)^3$$ and get a telescoping sum.



                                                                              i.e $$24sum_1^n k^2 +2n = sum_1^n (2k+1)^3-sum_1^n (2k-1)^3$$ $$24sum_1^n k^2 +2n = (2n+1)^3-1$$
                                                                              $$24sum_1^n k^2 =8 n^3+12 n^2+4 n$$ $$24sum_1^n k^2 =4 n (n+1) (2 n+1)$$ $$sum_1^n k^2 = frac{n (n+1) (2 n+1)}{6}$$






                                                                              share|cite|improve this answer











                                                                              $endgroup$



                                                                              The standard method is induction and you should look it up as it is a popular second example (first is $sum n$)



                                                                              Another argument is use: $$24n^2 +2= (2n+1)^3-(2n-1)^3$$ and get a telescoping sum.



                                                                              i.e $$24sum_1^n k^2 +2n = sum_1^n (2k+1)^3-sum_1^n (2k-1)^3$$ $$24sum_1^n k^2 +2n = (2n+1)^3-1$$
                                                                              $$24sum_1^n k^2 =8 n^3+12 n^2+4 n$$ $$24sum_1^n k^2 =4 n (n+1) (2 n+1)$$ $$sum_1^n k^2 = frac{n (n+1) (2 n+1)}{6}$$







                                                                              share|cite|improve this answer














                                                                              share|cite|improve this answer



                                                                              share|cite|improve this answer








                                                                              edited Jun 27 '11 at 23:19

























                                                                              answered Jun 27 '11 at 23:11









                                                                              kuch nahikuch nahi

                                                                              3,41053067




                                                                              3,41053067








                                                                              • 1




                                                                                $begingroup$
                                                                                For a combinatorial argument see Sivaram's answer here
                                                                                $endgroup$
                                                                                – kuch nahi
                                                                                Jun 27 '11 at 23:23














                                                                              • 1




                                                                                $begingroup$
                                                                                For a combinatorial argument see Sivaram's answer here
                                                                                $endgroup$
                                                                                – kuch nahi
                                                                                Jun 27 '11 at 23:23








                                                                              1




                                                                              1




                                                                              $begingroup$
                                                                              For a combinatorial argument see Sivaram's answer here
                                                                              $endgroup$
                                                                              – kuch nahi
                                                                              Jun 27 '11 at 23:23




                                                                              $begingroup$
                                                                              For a combinatorial argument see Sivaram's answer here
                                                                              $endgroup$
                                                                              – kuch nahi
                                                                              Jun 27 '11 at 23:23











                                                                              8












                                                                              $begingroup$

                                                                              Proof 1. (Exercise 2.5.1 in Dias Agudo, Cândido da Silva, Matemáticas Gerais III). Let $S:=sum_{k=1}^{n}k^{2}$. Consider $(1+a)^{3}=1+3a+3a^{2}+a^{3}$ and sum
                                                                              $(1+a)^{3}$ for $a=1,2,ldots ,n$:



                                                                              $$begin{eqnarray*}
                                                                              (1+1)^{3} &=&1+3cdot 1+3cdot 1^{2}+1^{3} \
                                                                              (1+2)^{3} &=&1+3cdot 2+3cdot 2^{2}+2^{3} \
                                                                              (1+3)^{3} &=&1+3cdot 3+3cdot 3^{2}+3^{3} \
                                                                              &&cdots \
                                                                              (1+n)^{3} &=&1+3cdot n+3cdot n^{2}+n^{3}
                                                                              end{eqnarray*}$$



                                                                              The term $(1+1)^3$ on the LHs of the 1st sum cancels the term $2^3$ on the RHS of the 2nd, $(1+2)^3$, the $3^3$, $(1+3)^4$, the $4^3$, ..., and $(1+n-1)^3$ cancels $n^3$. Hence



                                                                              $$(1+n)^{3}=n+3left( 1+2+ldots +nright) +3S+1$$



                                                                              and



                                                                              $$S=frac{n(n+1)(2n+1)}{6},$$



                                                                              because $1+2+ldots +n=dfrac{nleft( n+1right) }{2}$.



                                                                              Proof 2. (Exercise 1.42 in Balakrishnan, Combinatorics, Schaum's Outline of Combinatorics). From



                                                                              $$binom{k}{1}+2binom{k}{2}=k+2frac{kleft( k-1right) }{2}=k^{2},$$



                                                                              we get



                                                                              $$begin{eqnarray*}
                                                                              S &:&=sum_{k=1}^{n}k^{2}=sum_{k=1}^{n}binom{k}{1}+2binom{k}{2}
                                                                              =sum_{k=1}^{n}binom{k}{1}+2sum_{k=1}^{n}binom{k}{2} \
                                                                              &=&binom{n+1}{2}+2binom{n+1}{3} \
                                                                              &=&frac{nleft( n+1right) left( 2n+1right) }{6}.
                                                                              end{eqnarray*}$$






                                                                              share|cite|improve this answer











                                                                              $endgroup$


















                                                                                8












                                                                                $begingroup$

                                                                                Proof 1. (Exercise 2.5.1 in Dias Agudo, Cândido da Silva, Matemáticas Gerais III). Let $S:=sum_{k=1}^{n}k^{2}$. Consider $(1+a)^{3}=1+3a+3a^{2}+a^{3}$ and sum
                                                                                $(1+a)^{3}$ for $a=1,2,ldots ,n$:



                                                                                $$begin{eqnarray*}
                                                                                (1+1)^{3} &=&1+3cdot 1+3cdot 1^{2}+1^{3} \
                                                                                (1+2)^{3} &=&1+3cdot 2+3cdot 2^{2}+2^{3} \
                                                                                (1+3)^{3} &=&1+3cdot 3+3cdot 3^{2}+3^{3} \
                                                                                &&cdots \
                                                                                (1+n)^{3} &=&1+3cdot n+3cdot n^{2}+n^{3}
                                                                                end{eqnarray*}$$



                                                                                The term $(1+1)^3$ on the LHs of the 1st sum cancels the term $2^3$ on the RHS of the 2nd, $(1+2)^3$, the $3^3$, $(1+3)^4$, the $4^3$, ..., and $(1+n-1)^3$ cancels $n^3$. Hence



                                                                                $$(1+n)^{3}=n+3left( 1+2+ldots +nright) +3S+1$$



                                                                                and



                                                                                $$S=frac{n(n+1)(2n+1)}{6},$$



                                                                                because $1+2+ldots +n=dfrac{nleft( n+1right) }{2}$.



                                                                                Proof 2. (Exercise 1.42 in Balakrishnan, Combinatorics, Schaum's Outline of Combinatorics). From



                                                                                $$binom{k}{1}+2binom{k}{2}=k+2frac{kleft( k-1right) }{2}=k^{2},$$



                                                                                we get



                                                                                $$begin{eqnarray*}
                                                                                S &:&=sum_{k=1}^{n}k^{2}=sum_{k=1}^{n}binom{k}{1}+2binom{k}{2}
                                                                                =sum_{k=1}^{n}binom{k}{1}+2sum_{k=1}^{n}binom{k}{2} \
                                                                                &=&binom{n+1}{2}+2binom{n+1}{3} \
                                                                                &=&frac{nleft( n+1right) left( 2n+1right) }{6}.
                                                                                end{eqnarray*}$$






                                                                                share|cite|improve this answer











                                                                                $endgroup$
















                                                                                  8












                                                                                  8








                                                                                  8





                                                                                  $begingroup$

                                                                                  Proof 1. (Exercise 2.5.1 in Dias Agudo, Cândido da Silva, Matemáticas Gerais III). Let $S:=sum_{k=1}^{n}k^{2}$. Consider $(1+a)^{3}=1+3a+3a^{2}+a^{3}$ and sum
                                                                                  $(1+a)^{3}$ for $a=1,2,ldots ,n$:



                                                                                  $$begin{eqnarray*}
                                                                                  (1+1)^{3} &=&1+3cdot 1+3cdot 1^{2}+1^{3} \
                                                                                  (1+2)^{3} &=&1+3cdot 2+3cdot 2^{2}+2^{3} \
                                                                                  (1+3)^{3} &=&1+3cdot 3+3cdot 3^{2}+3^{3} \
                                                                                  &&cdots \
                                                                                  (1+n)^{3} &=&1+3cdot n+3cdot n^{2}+n^{3}
                                                                                  end{eqnarray*}$$



                                                                                  The term $(1+1)^3$ on the LHs of the 1st sum cancels the term $2^3$ on the RHS of the 2nd, $(1+2)^3$, the $3^3$, $(1+3)^4$, the $4^3$, ..., and $(1+n-1)^3$ cancels $n^3$. Hence



                                                                                  $$(1+n)^{3}=n+3left( 1+2+ldots +nright) +3S+1$$



                                                                                  and



                                                                                  $$S=frac{n(n+1)(2n+1)}{6},$$



                                                                                  because $1+2+ldots +n=dfrac{nleft( n+1right) }{2}$.



                                                                                  Proof 2. (Exercise 1.42 in Balakrishnan, Combinatorics, Schaum's Outline of Combinatorics). From



                                                                                  $$binom{k}{1}+2binom{k}{2}=k+2frac{kleft( k-1right) }{2}=k^{2},$$



                                                                                  we get



                                                                                  $$begin{eqnarray*}
                                                                                  S &:&=sum_{k=1}^{n}k^{2}=sum_{k=1}^{n}binom{k}{1}+2binom{k}{2}
                                                                                  =sum_{k=1}^{n}binom{k}{1}+2sum_{k=1}^{n}binom{k}{2} \
                                                                                  &=&binom{n+1}{2}+2binom{n+1}{3} \
                                                                                  &=&frac{nleft( n+1right) left( 2n+1right) }{6}.
                                                                                  end{eqnarray*}$$






                                                                                  share|cite|improve this answer











                                                                                  $endgroup$



                                                                                  Proof 1. (Exercise 2.5.1 in Dias Agudo, Cândido da Silva, Matemáticas Gerais III). Let $S:=sum_{k=1}^{n}k^{2}$. Consider $(1+a)^{3}=1+3a+3a^{2}+a^{3}$ and sum
                                                                                  $(1+a)^{3}$ for $a=1,2,ldots ,n$:



                                                                                  $$begin{eqnarray*}
                                                                                  (1+1)^{3} &=&1+3cdot 1+3cdot 1^{2}+1^{3} \
                                                                                  (1+2)^{3} &=&1+3cdot 2+3cdot 2^{2}+2^{3} \
                                                                                  (1+3)^{3} &=&1+3cdot 3+3cdot 3^{2}+3^{3} \
                                                                                  &&cdots \
                                                                                  (1+n)^{3} &=&1+3cdot n+3cdot n^{2}+n^{3}
                                                                                  end{eqnarray*}$$



                                                                                  The term $(1+1)^3$ on the LHs of the 1st sum cancels the term $2^3$ on the RHS of the 2nd, $(1+2)^3$, the $3^3$, $(1+3)^4$, the $4^3$, ..., and $(1+n-1)^3$ cancels $n^3$. Hence



                                                                                  $$(1+n)^{3}=n+3left( 1+2+ldots +nright) +3S+1$$



                                                                                  and



                                                                                  $$S=frac{n(n+1)(2n+1)}{6},$$



                                                                                  because $1+2+ldots +n=dfrac{nleft( n+1right) }{2}$.



                                                                                  Proof 2. (Exercise 1.42 in Balakrishnan, Combinatorics, Schaum's Outline of Combinatorics). From



                                                                                  $$binom{k}{1}+2binom{k}{2}=k+2frac{kleft( k-1right) }{2}=k^{2},$$



                                                                                  we get



                                                                                  $$begin{eqnarray*}
                                                                                  S &:&=sum_{k=1}^{n}k^{2}=sum_{k=1}^{n}binom{k}{1}+2binom{k}{2}
                                                                                  =sum_{k=1}^{n}binom{k}{1}+2sum_{k=1}^{n}binom{k}{2} \
                                                                                  &=&binom{n+1}{2}+2binom{n+1}{3} \
                                                                                  &=&frac{nleft( n+1right) left( 2n+1right) }{6}.
                                                                                  end{eqnarray*}$$







                                                                                  share|cite|improve this answer














                                                                                  share|cite|improve this answer



                                                                                  share|cite|improve this answer








                                                                                  edited Aug 4 '16 at 7:52

























                                                                                  answered Jul 10 '11 at 12:12









                                                                                  Américo TavaresAmérico Tavares

                                                                                  32.3k1080202




                                                                                  32.3k1080202























                                                                                      7












                                                                                      $begingroup$

                                                                                      Here's one using the Pertubation Method I learnt in Concrete Mathematics:
                                                                                      $$S_n = sum_{0leq jleq n}j^3$$.
                                                                                      $$S_n+(n+1)^3=sum_{0leq jleq n+1}j^3$$
                                                                                      $$S_n+(n+1)^3=0+sum_{1leq jleq n+1}j^3$$
                                                                                      Replacing $j$ by $j+1$ gives us
                                                                                      $$S_n+(n+1)^3=sum_{1leq j+1 leq n+1}(j+1)^3$$
                                                                                      Rewriting $1leq j+1leq n+1$ as $0leq jleq n$ and expanding$(j+1)^3$
                                                                                      $$S_n+(n+1)^3=sum_{0leq j leq n}(j^3+1+3j^2+3j)$$
                                                                                      By Associative law
                                                                                      $$S_n+(n+1)^3=sum_{0leq j leq n}j^3 +sum_{0leq jleq n}1 + 3sum_{0leq j leq n}j^2+3sum_{0leq jleq n}j$$
                                                                                      $S_n =sum_{0leq jleq n}j^3$, so it gets canceled.
                                                                                      Rewriting $sum_{0leq jleq n}1$ and $sum_{0leq jleq n}j$ as $(n+1)$ and $frac{n(n+1)}{2}$ respectively
                                                                                      $$(n+1)^3=(n+1)+frac{3n(n+1)}{2}+3sum_{0leq jleq n}j^2$$
                                                                                      $$3sum_{0leq jleq n}j^2=(n+1)^3-frac{3n(n+1)}{2} - (n+1)$$
                                                                                      $$3sum_{0leq jleq n}j^2=(n+1)(n^2+1+2n-frac{3n}{2}-1)$$
                                                                                      $$3sum_{0leq jleq n}j^2=frac{(n+1)(2n^2+n)}{2}$$
                                                                                      $$sum_{0leq jleq n}j^2=frac{n(n+1)(2n+1)}{6}$$
                                                                                      Using the same methods, one can get closed forms for even higher sums like $sum_{j=0}^{n}j^3$ by taking $S_n = sum_{0leq jleq n}j^4$ and using the binomial expansion for $(j+1)^4$






                                                                                      share|cite|improve this answer











                                                                                      $endgroup$













                                                                                      • $begingroup$
                                                                                        Same thing as Michael Lugo's answer, btw.
                                                                                        $endgroup$
                                                                                        – Bananach
                                                                                        Mar 3 '16 at 17:26
















                                                                                      7












                                                                                      $begingroup$

                                                                                      Here's one using the Pertubation Method I learnt in Concrete Mathematics:
                                                                                      $$S_n = sum_{0leq jleq n}j^3$$.
                                                                                      $$S_n+(n+1)^3=sum_{0leq jleq n+1}j^3$$
                                                                                      $$S_n+(n+1)^3=0+sum_{1leq jleq n+1}j^3$$
                                                                                      Replacing $j$ by $j+1$ gives us
                                                                                      $$S_n+(n+1)^3=sum_{1leq j+1 leq n+1}(j+1)^3$$
                                                                                      Rewriting $1leq j+1leq n+1$ as $0leq jleq n$ and expanding$(j+1)^3$
                                                                                      $$S_n+(n+1)^3=sum_{0leq j leq n}(j^3+1+3j^2+3j)$$
                                                                                      By Associative law
                                                                                      $$S_n+(n+1)^3=sum_{0leq j leq n}j^3 +sum_{0leq jleq n}1 + 3sum_{0leq j leq n}j^2+3sum_{0leq jleq n}j$$
                                                                                      $S_n =sum_{0leq jleq n}j^3$, so it gets canceled.
                                                                                      Rewriting $sum_{0leq jleq n}1$ and $sum_{0leq jleq n}j$ as $(n+1)$ and $frac{n(n+1)}{2}$ respectively
                                                                                      $$(n+1)^3=(n+1)+frac{3n(n+1)}{2}+3sum_{0leq jleq n}j^2$$
                                                                                      $$3sum_{0leq jleq n}j^2=(n+1)^3-frac{3n(n+1)}{2} - (n+1)$$
                                                                                      $$3sum_{0leq jleq n}j^2=(n+1)(n^2+1+2n-frac{3n}{2}-1)$$
                                                                                      $$3sum_{0leq jleq n}j^2=frac{(n+1)(2n^2+n)}{2}$$
                                                                                      $$sum_{0leq jleq n}j^2=frac{n(n+1)(2n+1)}{6}$$
                                                                                      Using the same methods, one can get closed forms for even higher sums like $sum_{j=0}^{n}j^3$ by taking $S_n = sum_{0leq jleq n}j^4$ and using the binomial expansion for $(j+1)^4$






                                                                                      share|cite|improve this answer











                                                                                      $endgroup$













                                                                                      • $begingroup$
                                                                                        Same thing as Michael Lugo's answer, btw.
                                                                                        $endgroup$
                                                                                        – Bananach
                                                                                        Mar 3 '16 at 17:26














                                                                                      7












                                                                                      7








                                                                                      7





                                                                                      $begingroup$

                                                                                      Here's one using the Pertubation Method I learnt in Concrete Mathematics:
                                                                                      $$S_n = sum_{0leq jleq n}j^3$$.
                                                                                      $$S_n+(n+1)^3=sum_{0leq jleq n+1}j^3$$
                                                                                      $$S_n+(n+1)^3=0+sum_{1leq jleq n+1}j^3$$
                                                                                      Replacing $j$ by $j+1$ gives us
                                                                                      $$S_n+(n+1)^3=sum_{1leq j+1 leq n+1}(j+1)^3$$
                                                                                      Rewriting $1leq j+1leq n+1$ as $0leq jleq n$ and expanding$(j+1)^3$
                                                                                      $$S_n+(n+1)^3=sum_{0leq j leq n}(j^3+1+3j^2+3j)$$
                                                                                      By Associative law
                                                                                      $$S_n+(n+1)^3=sum_{0leq j leq n}j^3 +sum_{0leq jleq n}1 + 3sum_{0leq j leq n}j^2+3sum_{0leq jleq n}j$$
                                                                                      $S_n =sum_{0leq jleq n}j^3$, so it gets canceled.
                                                                                      Rewriting $sum_{0leq jleq n}1$ and $sum_{0leq jleq n}j$ as $(n+1)$ and $frac{n(n+1)}{2}$ respectively
                                                                                      $$(n+1)^3=(n+1)+frac{3n(n+1)}{2}+3sum_{0leq jleq n}j^2$$
                                                                                      $$3sum_{0leq jleq n}j^2=(n+1)^3-frac{3n(n+1)}{2} - (n+1)$$
                                                                                      $$3sum_{0leq jleq n}j^2=(n+1)(n^2+1+2n-frac{3n}{2}-1)$$
                                                                                      $$3sum_{0leq jleq n}j^2=frac{(n+1)(2n^2+n)}{2}$$
                                                                                      $$sum_{0leq jleq n}j^2=frac{n(n+1)(2n+1)}{6}$$
                                                                                      Using the same methods, one can get closed forms for even higher sums like $sum_{j=0}^{n}j^3$ by taking $S_n = sum_{0leq jleq n}j^4$ and using the binomial expansion for $(j+1)^4$






                                                                                      share|cite|improve this answer











                                                                                      $endgroup$



                                                                                      Here's one using the Pertubation Method I learnt in Concrete Mathematics:
                                                                                      $$S_n = sum_{0leq jleq n}j^3$$.
                                                                                      $$S_n+(n+1)^3=sum_{0leq jleq n+1}j^3$$
                                                                                      $$S_n+(n+1)^3=0+sum_{1leq jleq n+1}j^3$$
                                                                                      Replacing $j$ by $j+1$ gives us
                                                                                      $$S_n+(n+1)^3=sum_{1leq j+1 leq n+1}(j+1)^3$$
                                                                                      Rewriting $1leq j+1leq n+1$ as $0leq jleq n$ and expanding$(j+1)^3$
                                                                                      $$S_n+(n+1)^3=sum_{0leq j leq n}(j^3+1+3j^2+3j)$$
                                                                                      By Associative law
                                                                                      $$S_n+(n+1)^3=sum_{0leq j leq n}j^3 +sum_{0leq jleq n}1 + 3sum_{0leq j leq n}j^2+3sum_{0leq jleq n}j$$
                                                                                      $S_n =sum_{0leq jleq n}j^3$, so it gets canceled.
                                                                                      Rewriting $sum_{0leq jleq n}1$ and $sum_{0leq jleq n}j$ as $(n+1)$ and $frac{n(n+1)}{2}$ respectively
                                                                                      $$(n+1)^3=(n+1)+frac{3n(n+1)}{2}+3sum_{0leq jleq n}j^2$$
                                                                                      $$3sum_{0leq jleq n}j^2=(n+1)^3-frac{3n(n+1)}{2} - (n+1)$$
                                                                                      $$3sum_{0leq jleq n}j^2=(n+1)(n^2+1+2n-frac{3n}{2}-1)$$
                                                                                      $$3sum_{0leq jleq n}j^2=frac{(n+1)(2n^2+n)}{2}$$
                                                                                      $$sum_{0leq jleq n}j^2=frac{n(n+1)(2n+1)}{6}$$
                                                                                      Using the same methods, one can get closed forms for even higher sums like $sum_{j=0}^{n}j^3$ by taking $S_n = sum_{0leq jleq n}j^4$ and using the binomial expansion for $(j+1)^4$







                                                                                      share|cite|improve this answer














                                                                                      share|cite|improve this answer



                                                                                      share|cite|improve this answer








                                                                                      edited Feb 23 '14 at 4:32

























                                                                                      answered Feb 23 '14 at 4:24









                                                                                      Vibhav PantVibhav Pant

                                                                                      462318




                                                                                      462318












                                                                                      • $begingroup$
                                                                                        Same thing as Michael Lugo's answer, btw.
                                                                                        $endgroup$
                                                                                        – Bananach
                                                                                        Mar 3 '16 at 17:26


















                                                                                      • $begingroup$
                                                                                        Same thing as Michael Lugo's answer, btw.
                                                                                        $endgroup$
                                                                                        – Bananach
                                                                                        Mar 3 '16 at 17:26
















                                                                                      $begingroup$
                                                                                      Same thing as Michael Lugo's answer, btw.
                                                                                      $endgroup$
                                                                                      – Bananach
                                                                                      Mar 3 '16 at 17:26




                                                                                      $begingroup$
                                                                                      Same thing as Michael Lugo's answer, btw.
                                                                                      $endgroup$
                                                                                      – Bananach
                                                                                      Mar 3 '16 at 17:26











                                                                                      6












                                                                                      $begingroup$

                                                                                      A combinatorial proof:



                                                                                      Let $S={1,2,dots,(n+1)},nge 2$ and $T={(x,y,z)|x.y,zin S,x< z,y< z}$.By counting the number of members of $T$ in $2$ different ways I will prove the formula.



                                                                                      $1$st way:



                                                                                      We will at first Choose $z$ form the set $S$.When $z$ is $1$ then there are no choices for $x,y$ so the no. of elements of $T$ with $z=0$ is zero.When $z=2$ the number of choices for $x$ is $1$ and so is for $y$(precisely $x=y=1$).When $z=3$ then $xin {1,2}$ and $yin {1,2}$ so total no. of choices equals $2^2$.In a similar manner when $z=k,(1le kle (n+1))$,no. of choices for $x$ equals $(k-1)$ and no. of choices for $y$ is also $(k-1)$. So total no . of elements of T with $z=k$ is $(k-1)^2$.



                                                                                      So we will get the total no. of elements of $T$ by summing $(k-1)^2$ up from $1 $ to $(n+1)$.Hence $$|T|=sum _{l=1}^{(n+1)}(l-1)^2=sum_{k=1}^{n}k^2$$



                                                                                      $2$nd way:



                                                                                      Among the elements of $T$ consisting of three numbers from the set $S$, there are elements in $x=y$ and elements in which $xne y$.



                                                                                      We can count the no. of elements in which $x=y$ by choosing two distinct nos. from $S$ and assigning $z$ with the lagest no. and $x,y$ with the smallest number. We can choose two distinct numbers from $S$ in $displaystyle binom{n+1}{2}$ ways, so the total no. elements having $x=y$ is $displaystyle binom{n+1}{2}$.



                                                                                      Now we have to count the number of elements in which $xne y$.This means that $x,y$ are dinstict and as they are less than $z$ this means that all the three are distinct. So we can count no. of such elements in $T$ in the following way.At first we will choose three elements from the set $S$ and assign the largest value to $z$ and assign the other two values to $x,y$. Now we can choose three numbers from the set $S$ in $displaystyle binom{n+1}{3}$.From each such three element we can get two elements of the set $T$(Assigning the largest to $z$ and then assigning any one of then to $x$ and the other to $y$). So no. of elements of $T$ having $xne y$ is $2displaystyle binom{n+1}{3}$



                                                                                      So by this method we have $|T|=displaystyle binom{n+1}{2}+2displaystyle binom{n+1}{3}$



                                                                                      On equating the result obtained from both the methods we have
                                                                                      $$sum_{k=1}^{n}k^2=displaystyle binom{n+1}{2}+2displaystyle binom{n+1}{3}=frac{n(n+1)(2n+1)}{6}$$



                                                                                      Note that this can easily be extended to find the sum of $p$th power of integers.($pin mathbb{N})$






                                                                                      share|cite|improve this answer









                                                                                      $endgroup$


















                                                                                        6












                                                                                        $begingroup$

                                                                                        A combinatorial proof:



                                                                                        Let $S={1,2,dots,(n+1)},nge 2$ and $T={(x,y,z)|x.y,zin S,x< z,y< z}$.By counting the number of members of $T$ in $2$ different ways I will prove the formula.



                                                                                        $1$st way:



                                                                                        We will at first Choose $z$ form the set $S$.When $z$ is $1$ then there are no choices for $x,y$ so the no. of elements of $T$ with $z=0$ is zero.When $z=2$ the number of choices for $x$ is $1$ and so is for $y$(precisely $x=y=1$).When $z=3$ then $xin {1,2}$ and $yin {1,2}$ so total no. of choices equals $2^2$.In a similar manner when $z=k,(1le kle (n+1))$,no. of choices for $x$ equals $(k-1)$ and no. of choices for $y$ is also $(k-1)$. So total no . of elements of T with $z=k$ is $(k-1)^2$.



                                                                                        So we will get the total no. of elements of $T$ by summing $(k-1)^2$ up from $1 $ to $(n+1)$.Hence $$|T|=sum _{l=1}^{(n+1)}(l-1)^2=sum_{k=1}^{n}k^2$$



                                                                                        $2$nd way:



                                                                                        Among the elements of $T$ consisting of three numbers from the set $S$, there are elements in $x=y$ and elements in which $xne y$.



                                                                                        We can count the no. of elements in which $x=y$ by choosing two distinct nos. from $S$ and assigning $z$ with the lagest no. and $x,y$ with the smallest number. We can choose two distinct numbers from $S$ in $displaystyle binom{n+1}{2}$ ways, so the total no. elements having $x=y$ is $displaystyle binom{n+1}{2}$.



                                                                                        Now we have to count the number of elements in which $xne y$.This means that $x,y$ are dinstict and as they are less than $z$ this means that all the three are distinct. So we can count no. of such elements in $T$ in the following way.At first we will choose three elements from the set $S$ and assign the largest value to $z$ and assign the other two values to $x,y$. Now we can choose three numbers from the set $S$ in $displaystyle binom{n+1}{3}$.From each such three element we can get two elements of the set $T$(Assigning the largest to $z$ and then assigning any one of then to $x$ and the other to $y$). So no. of elements of $T$ having $xne y$ is $2displaystyle binom{n+1}{3}$



                                                                                        So by this method we have $|T|=displaystyle binom{n+1}{2}+2displaystyle binom{n+1}{3}$



                                                                                        On equating the result obtained from both the methods we have
                                                                                        $$sum_{k=1}^{n}k^2=displaystyle binom{n+1}{2}+2displaystyle binom{n+1}{3}=frac{n(n+1)(2n+1)}{6}$$



                                                                                        Note that this can easily be extended to find the sum of $p$th power of integers.($pin mathbb{N})$






                                                                                        share|cite|improve this answer









                                                                                        $endgroup$
















                                                                                          6












                                                                                          6








                                                                                          6





                                                                                          $begingroup$

                                                                                          A combinatorial proof:



                                                                                          Let $S={1,2,dots,(n+1)},nge 2$ and $T={(x,y,z)|x.y,zin S,x< z,y< z}$.By counting the number of members of $T$ in $2$ different ways I will prove the formula.



                                                                                          $1$st way:



                                                                                          We will at first Choose $z$ form the set $S$.When $z$ is $1$ then there are no choices for $x,y$ so the no. of elements of $T$ with $z=0$ is zero.When $z=2$ the number of choices for $x$ is $1$ and so is for $y$(precisely $x=y=1$).When $z=3$ then $xin {1,2}$ and $yin {1,2}$ so total no. of choices equals $2^2$.In a similar manner when $z=k,(1le kle (n+1))$,no. of choices for $x$ equals $(k-1)$ and no. of choices for $y$ is also $(k-1)$. So total no . of elements of T with $z=k$ is $(k-1)^2$.



                                                                                          So we will get the total no. of elements of $T$ by summing $(k-1)^2$ up from $1 $ to $(n+1)$.Hence $$|T|=sum _{l=1}^{(n+1)}(l-1)^2=sum_{k=1}^{n}k^2$$



                                                                                          $2$nd way:



                                                                                          Among the elements of $T$ consisting of three numbers from the set $S$, there are elements in $x=y$ and elements in which $xne y$.



                                                                                          We can count the no. of elements in which $x=y$ by choosing two distinct nos. from $S$ and assigning $z$ with the lagest no. and $x,y$ with the smallest number. We can choose two distinct numbers from $S$ in $displaystyle binom{n+1}{2}$ ways, so the total no. elements having $x=y$ is $displaystyle binom{n+1}{2}$.



                                                                                          Now we have to count the number of elements in which $xne y$.This means that $x,y$ are dinstict and as they are less than $z$ this means that all the three are distinct. So we can count no. of such elements in $T$ in the following way.At first we will choose three elements from the set $S$ and assign the largest value to $z$ and assign the other two values to $x,y$. Now we can choose three numbers from the set $S$ in $displaystyle binom{n+1}{3}$.From each such three element we can get two elements of the set $T$(Assigning the largest to $z$ and then assigning any one of then to $x$ and the other to $y$). So no. of elements of $T$ having $xne y$ is $2displaystyle binom{n+1}{3}$



                                                                                          So by this method we have $|T|=displaystyle binom{n+1}{2}+2displaystyle binom{n+1}{3}$



                                                                                          On equating the result obtained from both the methods we have
                                                                                          $$sum_{k=1}^{n}k^2=displaystyle binom{n+1}{2}+2displaystyle binom{n+1}{3}=frac{n(n+1)(2n+1)}{6}$$



                                                                                          Note that this can easily be extended to find the sum of $p$th power of integers.($pin mathbb{N})$






                                                                                          share|cite|improve this answer









                                                                                          $endgroup$



                                                                                          A combinatorial proof:



                                                                                          Let $S={1,2,dots,(n+1)},nge 2$ and $T={(x,y,z)|x.y,zin S,x< z,y< z}$.By counting the number of members of $T$ in $2$ different ways I will prove the formula.



                                                                                          $1$st way:



                                                                                          We will at first Choose $z$ form the set $S$.When $z$ is $1$ then there are no choices for $x,y$ so the no. of elements of $T$ with $z=0$ is zero.When $z=2$ the number of choices for $x$ is $1$ and so is for $y$(precisely $x=y=1$).When $z=3$ then $xin {1,2}$ and $yin {1,2}$ so total no. of choices equals $2^2$.In a similar manner when $z=k,(1le kle (n+1))$,no. of choices for $x$ equals $(k-1)$ and no. of choices for $y$ is also $(k-1)$. So total no . of elements of T with $z=k$ is $(k-1)^2$.



                                                                                          So we will get the total no. of elements of $T$ by summing $(k-1)^2$ up from $1 $ to $(n+1)$.Hence $$|T|=sum _{l=1}^{(n+1)}(l-1)^2=sum_{k=1}^{n}k^2$$



                                                                                          $2$nd way:



                                                                                          Among the elements of $T$ consisting of three numbers from the set $S$, there are elements in $x=y$ and elements in which $xne y$.



                                                                                          We can count the no. of elements in which $x=y$ by choosing two distinct nos. from $S$ and assigning $z$ with the lagest no. and $x,y$ with the smallest number. We can choose two distinct numbers from $S$ in $displaystyle binom{n+1}{2}$ ways, so the total no. elements having $x=y$ is $displaystyle binom{n+1}{2}$.



                                                                                          Now we have to count the number of elements in which $xne y$.This means that $x,y$ are dinstict and as they are less than $z$ this means that all the three are distinct. So we can count no. of such elements in $T$ in the following way.At first we will choose three elements from the set $S$ and assign the largest value to $z$ and assign the other two values to $x,y$. Now we can choose three numbers from the set $S$ in $displaystyle binom{n+1}{3}$.From each such three element we can get two elements of the set $T$(Assigning the largest to $z$ and then assigning any one of then to $x$ and the other to $y$). So no. of elements of $T$ having $xne y$ is $2displaystyle binom{n+1}{3}$



                                                                                          So by this method we have $|T|=displaystyle binom{n+1}{2}+2displaystyle binom{n+1}{3}$



                                                                                          On equating the result obtained from both the methods we have
                                                                                          $$sum_{k=1}^{n}k^2=displaystyle binom{n+1}{2}+2displaystyle binom{n+1}{3}=frac{n(n+1)(2n+1)}{6}$$



                                                                                          Note that this can easily be extended to find the sum of $p$th power of integers.($pin mathbb{N})$







                                                                                          share|cite|improve this answer












                                                                                          share|cite|improve this answer



                                                                                          share|cite|improve this answer










                                                                                          answered May 28 '13 at 6:43









                                                                                          Abhra Abir KunduAbhra Abir Kundu

                                                                                          7,1941328




                                                                                          7,1941328























                                                                                              5












                                                                                              $begingroup$

                                                                                              Another simple proof could be as follows: note that each square
                                                                                              can be written as a sum of odd numbers:



                                                                                              $sum_{k=1}^n(2k-1)=n^2$.



                                                                                              (that can be easily shown)



                                                                                              When writing each square as a sum of odd numbers we get that



                                                                                              $S=sum_{k=1}^n k^2=1 + (1+3) + (1+3+5) + ... =sum_{k=1}^n(n-k+1)(2k-1)=$



                                                                                              $=(2n+3)sum_{k=1}^n k -(n+1)sum_{k=1}^n 1 -2S$.



                                                                                              Therefore



                                                                                              $3S=frac{(2n+3)n(n+1)}{2}-n(n+1)=frac{(2n+1)n(n+1)}{2}$.






                                                                                              share|cite|improve this answer









                                                                                              $endgroup$


















                                                                                                5












                                                                                                $begingroup$

                                                                                                Another simple proof could be as follows: note that each square
                                                                                                can be written as a sum of odd numbers:



                                                                                                $sum_{k=1}^n(2k-1)=n^2$.



                                                                                                (that can be easily shown)



                                                                                                When writing each square as a sum of odd numbers we get that



                                                                                                $S=sum_{k=1}^n k^2=1 + (1+3) + (1+3+5) + ... =sum_{k=1}^n(n-k+1)(2k-1)=$



                                                                                                $=(2n+3)sum_{k=1}^n k -(n+1)sum_{k=1}^n 1 -2S$.



                                                                                                Therefore



                                                                                                $3S=frac{(2n+3)n(n+1)}{2}-n(n+1)=frac{(2n+1)n(n+1)}{2}$.






                                                                                                share|cite|improve this answer









                                                                                                $endgroup$
















                                                                                                  5












                                                                                                  5








                                                                                                  5





                                                                                                  $begingroup$

                                                                                                  Another simple proof could be as follows: note that each square
                                                                                                  can be written as a sum of odd numbers:



                                                                                                  $sum_{k=1}^n(2k-1)=n^2$.



                                                                                                  (that can be easily shown)



                                                                                                  When writing each square as a sum of odd numbers we get that



                                                                                                  $S=sum_{k=1}^n k^2=1 + (1+3) + (1+3+5) + ... =sum_{k=1}^n(n-k+1)(2k-1)=$



                                                                                                  $=(2n+3)sum_{k=1}^n k -(n+1)sum_{k=1}^n 1 -2S$.



                                                                                                  Therefore



                                                                                                  $3S=frac{(2n+3)n(n+1)}{2}-n(n+1)=frac{(2n+1)n(n+1)}{2}$.






                                                                                                  share|cite|improve this answer









                                                                                                  $endgroup$



                                                                                                  Another simple proof could be as follows: note that each square
                                                                                                  can be written as a sum of odd numbers:



                                                                                                  $sum_{k=1}^n(2k-1)=n^2$.



                                                                                                  (that can be easily shown)



                                                                                                  When writing each square as a sum of odd numbers we get that



                                                                                                  $S=sum_{k=1}^n k^2=1 + (1+3) + (1+3+5) + ... =sum_{k=1}^n(n-k+1)(2k-1)=$



                                                                                                  $=(2n+3)sum_{k=1}^n k -(n+1)sum_{k=1}^n 1 -2S$.



                                                                                                  Therefore



                                                                                                  $3S=frac{(2n+3)n(n+1)}{2}-n(n+1)=frac{(2n+1)n(n+1)}{2}$.







                                                                                                  share|cite|improve this answer












                                                                                                  share|cite|improve this answer



                                                                                                  share|cite|improve this answer










                                                                                                  answered Oct 17 '13 at 13:02









                                                                                                  school-mateschool-mate

                                                                                                  5111




                                                                                                  5111























                                                                                                      4












                                                                                                      $begingroup$

                                                                                                      $begin{aligned} & hspace{0.5in} begin{aligned}displaystyle sum_{1 le k le n}k^2 & = sum_{1 le k le n}~sum_{1 le r le k}r =sum_{1 le r le n}~sum_{r le k le n}r \& = sum_{1 le r le n}~sum_{1 le k le n}r-sum_{1 le r le n}~sum_{1 le k le r-1}r \& = nsum_{1 le r le n}r-frac{1}{2}sum_{1 le r le n}r(r-1) \& =frac{1}{2}n^2(n+1)-frac{1}{2}sum_{1 le r le n}r^2+frac{1}{2}sum_{1 le r le n}r \& =frac{1}{2}n^2(n+1)-frac{1}{2}sum_{1 le k le n}k^2+frac{1}{4}n(n+1) end{aligned} \& begin{aligned}impliesfrac{3}{2}sum_{1 le k le n}k^2 & = frac{1}{2}n^2(n+1)+frac{1}{4}n(n+1) \& = frac{1}{4}n(n+1)(2n+1) end{aligned}\& implies hspace{0.15in} displaystyle sum_{1 le k le n}k^2 = frac{1}{6}n(n+1)(2n+1).end{aligned}$






                                                                                                      share|cite|improve this answer









                                                                                                      $endgroup$













                                                                                                      • $begingroup$
                                                                                                        This is an approach that I like. It can be generalized to $$begin{align}f(n, m) &= sum_{k = 1}^n k^m \&= sum_{k = 1}^n sum_{r = 1}^k k^{m-1} \&= sum_{1 le r le k le n} k^{m-1} \&= sum_{r = 1}^n sum_{k=r}^n k^{m-1} \&= sum_{r=1}^n f(n, m-1 ) - f(r - 1 , m - 1) end{align}$$ to be able to recursively solve any case.
                                                                                                        $endgroup$
                                                                                                        – DanielV
                                                                                                        Jan 11 '16 at 13:50
















                                                                                                      4












                                                                                                      $begingroup$

                                                                                                      $begin{aligned} & hspace{0.5in} begin{aligned}displaystyle sum_{1 le k le n}k^2 & = sum_{1 le k le n}~sum_{1 le r le k}r =sum_{1 le r le n}~sum_{r le k le n}r \& = sum_{1 le r le n}~sum_{1 le k le n}r-sum_{1 le r le n}~sum_{1 le k le r-1}r \& = nsum_{1 le r le n}r-frac{1}{2}sum_{1 le r le n}r(r-1) \& =frac{1}{2}n^2(n+1)-frac{1}{2}sum_{1 le r le n}r^2+frac{1}{2}sum_{1 le r le n}r \& =frac{1}{2}n^2(n+1)-frac{1}{2}sum_{1 le k le n}k^2+frac{1}{4}n(n+1) end{aligned} \& begin{aligned}impliesfrac{3}{2}sum_{1 le k le n}k^2 & = frac{1}{2}n^2(n+1)+frac{1}{4}n(n+1) \& = frac{1}{4}n(n+1)(2n+1) end{aligned}\& implies hspace{0.15in} displaystyle sum_{1 le k le n}k^2 = frac{1}{6}n(n+1)(2n+1).end{aligned}$






                                                                                                      share|cite|improve this answer









                                                                                                      $endgroup$













                                                                                                      • $begingroup$
                                                                                                        This is an approach that I like. It can be generalized to $$begin{align}f(n, m) &= sum_{k = 1}^n k^m \&= sum_{k = 1}^n sum_{r = 1}^k k^{m-1} \&= sum_{1 le r le k le n} k^{m-1} \&= sum_{r = 1}^n sum_{k=r}^n k^{m-1} \&= sum_{r=1}^n f(n, m-1 ) - f(r - 1 , m - 1) end{align}$$ to be able to recursively solve any case.
                                                                                                        $endgroup$
                                                                                                        – DanielV
                                                                                                        Jan 11 '16 at 13:50














                                                                                                      4












                                                                                                      4








                                                                                                      4





                                                                                                      $begingroup$

                                                                                                      $begin{aligned} & hspace{0.5in} begin{aligned}displaystyle sum_{1 le k le n}k^2 & = sum_{1 le k le n}~sum_{1 le r le k}r =sum_{1 le r le n}~sum_{r le k le n}r \& = sum_{1 le r le n}~sum_{1 le k le n}r-sum_{1 le r le n}~sum_{1 le k le r-1}r \& = nsum_{1 le r le n}r-frac{1}{2}sum_{1 le r le n}r(r-1) \& =frac{1}{2}n^2(n+1)-frac{1}{2}sum_{1 le r le n}r^2+frac{1}{2}sum_{1 le r le n}r \& =frac{1}{2}n^2(n+1)-frac{1}{2}sum_{1 le k le n}k^2+frac{1}{4}n(n+1) end{aligned} \& begin{aligned}impliesfrac{3}{2}sum_{1 le k le n}k^2 & = frac{1}{2}n^2(n+1)+frac{1}{4}n(n+1) \& = frac{1}{4}n(n+1)(2n+1) end{aligned}\& implies hspace{0.15in} displaystyle sum_{1 le k le n}k^2 = frac{1}{6}n(n+1)(2n+1).end{aligned}$






                                                                                                      share|cite|improve this answer









                                                                                                      $endgroup$



                                                                                                      $begin{aligned} & hspace{0.5in} begin{aligned}displaystyle sum_{1 le k le n}k^2 & = sum_{1 le k le n}~sum_{1 le r le k}r =sum_{1 le r le n}~sum_{r le k le n}r \& = sum_{1 le r le n}~sum_{1 le k le n}r-sum_{1 le r le n}~sum_{1 le k le r-1}r \& = nsum_{1 le r le n}r-frac{1}{2}sum_{1 le r le n}r(r-1) \& =frac{1}{2}n^2(n+1)-frac{1}{2}sum_{1 le r le n}r^2+frac{1}{2}sum_{1 le r le n}r \& =frac{1}{2}n^2(n+1)-frac{1}{2}sum_{1 le k le n}k^2+frac{1}{4}n(n+1) end{aligned} \& begin{aligned}impliesfrac{3}{2}sum_{1 le k le n}k^2 & = frac{1}{2}n^2(n+1)+frac{1}{4}n(n+1) \& = frac{1}{4}n(n+1)(2n+1) end{aligned}\& implies hspace{0.15in} displaystyle sum_{1 le k le n}k^2 = frac{1}{6}n(n+1)(2n+1).end{aligned}$







                                                                                                      share|cite|improve this answer












                                                                                                      share|cite|improve this answer



                                                                                                      share|cite|improve this answer










                                                                                                      answered Sep 18 '11 at 15:34









                                                                                                      NeverBeenHereNeverBeenHere

                                                                                                      797613




                                                                                                      797613












                                                                                                      • $begingroup$
                                                                                                        This is an approach that I like. It can be generalized to $$begin{align}f(n, m) &= sum_{k = 1}^n k^m \&= sum_{k = 1}^n sum_{r = 1}^k k^{m-1} \&= sum_{1 le r le k le n} k^{m-1} \&= sum_{r = 1}^n sum_{k=r}^n k^{m-1} \&= sum_{r=1}^n f(n, m-1 ) - f(r - 1 , m - 1) end{align}$$ to be able to recursively solve any case.
                                                                                                        $endgroup$
                                                                                                        – DanielV
                                                                                                        Jan 11 '16 at 13:50


















                                                                                                      • $begingroup$
                                                                                                        This is an approach that I like. It can be generalized to $$begin{align}f(n, m) &= sum_{k = 1}^n k^m \&= sum_{k = 1}^n sum_{r = 1}^k k^{m-1} \&= sum_{1 le r le k le n} k^{m-1} \&= sum_{r = 1}^n sum_{k=r}^n k^{m-1} \&= sum_{r=1}^n f(n, m-1 ) - f(r - 1 , m - 1) end{align}$$ to be able to recursively solve any case.
                                                                                                        $endgroup$
                                                                                                        – DanielV
                                                                                                        Jan 11 '16 at 13:50
















                                                                                                      $begingroup$
                                                                                                      This is an approach that I like. It can be generalized to $$begin{align}f(n, m) &= sum_{k = 1}^n k^m \&= sum_{k = 1}^n sum_{r = 1}^k k^{m-1} \&= sum_{1 le r le k le n} k^{m-1} \&= sum_{r = 1}^n sum_{k=r}^n k^{m-1} \&= sum_{r=1}^n f(n, m-1 ) - f(r - 1 , m - 1) end{align}$$ to be able to recursively solve any case.
                                                                                                      $endgroup$
                                                                                                      – DanielV
                                                                                                      Jan 11 '16 at 13:50




                                                                                                      $begingroup$
                                                                                                      This is an approach that I like. It can be generalized to $$begin{align}f(n, m) &= sum_{k = 1}^n k^m \&= sum_{k = 1}^n sum_{r = 1}^k k^{m-1} \&= sum_{1 le r le k le n} k^{m-1} \&= sum_{r = 1}^n sum_{k=r}^n k^{m-1} \&= sum_{r=1}^n f(n, m-1 ) - f(r - 1 , m - 1) end{align}$$ to be able to recursively solve any case.
                                                                                                      $endgroup$
                                                                                                      – DanielV
                                                                                                      Jan 11 '16 at 13:50











                                                                                                      3












                                                                                                      $begingroup$

                                                                                                      Yet another take. Start with the definition of falling factorial powers:



                                                                                                      $begin{align}
                                                                                                      x^{underline{r}}
                                                                                                      = x (x - 1) dotsm (x - r + 1)
                                                                                                      end{align}$



                                                                                                      so that:



                                                                                                      $begin{align}
                                                                                                      Delta n^{underline{r}}
                                                                                                      &= (n + 1)^{underline{r}} - n^{underline{r}} \
                                                                                                      &= r n^{underline{r - 1}} \
                                                                                                      sum_{0 le k < n} k^{underline{r}}
                                                                                                      &= frac{n^{underline{r + 1}}}{r + 1}
                                                                                                      end{align}$



                                                                                                      (the last one is also easy to prove by induction, or otherwise).





                                                                                                      Now note that:



                                                                                                      $begin{align}
                                                                                                      n^2
                                                                                                      = n^{underline{2}} + n^{underline{1}}
                                                                                                      end{align}$



                                                                                                      so we can write:



                                                                                                      $begin{align}
                                                                                                      sum_{0 le k le n} k^2
                                                                                                      &= sum_{0 le k < n + 1}
                                                                                                      left( k^{underline{2}} + k^{underline{1}} right) \
                                                                                                      &= frac{(n + 1)^{underline{3}}}{3}
                                                                                                      + frac{(n + 1)^{underline{2}}}{2} \
                                                                                                      &= frac{(n + 1) n (n - 1)}{3} + frac{(n + 1) n}{2} \
                                                                                                      &= frac{(2 n + 1) (n + 1) n}{6}
                                                                                                      end{align}$






                                                                                                      share|cite|improve this answer









                                                                                                      $endgroup$


















                                                                                                        3












                                                                                                        $begingroup$

                                                                                                        Yet another take. Start with the definition of falling factorial powers:



                                                                                                        $begin{align}
                                                                                                        x^{underline{r}}
                                                                                                        = x (x - 1) dotsm (x - r + 1)
                                                                                                        end{align}$



                                                                                                        so that:



                                                                                                        $begin{align}
                                                                                                        Delta n^{underline{r}}
                                                                                                        &= (n + 1)^{underline{r}} - n^{underline{r}} \
                                                                                                        &= r n^{underline{r - 1}} \
                                                                                                        sum_{0 le k < n} k^{underline{r}}
                                                                                                        &= frac{n^{underline{r + 1}}}{r + 1}
                                                                                                        end{align}$



                                                                                                        (the last one is also easy to prove by induction, or otherwise).





                                                                                                        Now note that:



                                                                                                        $begin{align}
                                                                                                        n^2
                                                                                                        = n^{underline{2}} + n^{underline{1}}
                                                                                                        end{align}$



                                                                                                        so we can write:



                                                                                                        $begin{align}
                                                                                                        sum_{0 le k le n} k^2
                                                                                                        &= sum_{0 le k < n + 1}
                                                                                                        left( k^{underline{2}} + k^{underline{1}} right) \
                                                                                                        &= frac{(n + 1)^{underline{3}}}{3}
                                                                                                        + frac{(n + 1)^{underline{2}}}{2} \
                                                                                                        &= frac{(n + 1) n (n - 1)}{3} + frac{(n + 1) n}{2} \
                                                                                                        &= frac{(2 n + 1) (n + 1) n}{6}
                                                                                                        end{align}$






                                                                                                        share|cite|improve this answer









                                                                                                        $endgroup$
















                                                                                                          3












                                                                                                          3








                                                                                                          3





                                                                                                          $begingroup$

                                                                                                          Yet another take. Start with the definition of falling factorial powers:



                                                                                                          $begin{align}
                                                                                                          x^{underline{r}}
                                                                                                          = x (x - 1) dotsm (x - r + 1)
                                                                                                          end{align}$



                                                                                                          so that:



                                                                                                          $begin{align}
                                                                                                          Delta n^{underline{r}}
                                                                                                          &= (n + 1)^{underline{r}} - n^{underline{r}} \
                                                                                                          &= r n^{underline{r - 1}} \
                                                                                                          sum_{0 le k < n} k^{underline{r}}
                                                                                                          &= frac{n^{underline{r + 1}}}{r + 1}
                                                                                                          end{align}$



                                                                                                          (the last one is also easy to prove by induction, or otherwise).





                                                                                                          Now note that:



                                                                                                          $begin{align}
                                                                                                          n^2
                                                                                                          = n^{underline{2}} + n^{underline{1}}
                                                                                                          end{align}$



                                                                                                          so we can write:



                                                                                                          $begin{align}
                                                                                                          sum_{0 le k le n} k^2
                                                                                                          &= sum_{0 le k < n + 1}
                                                                                                          left( k^{underline{2}} + k^{underline{1}} right) \
                                                                                                          &= frac{(n + 1)^{underline{3}}}{3}
                                                                                                          + frac{(n + 1)^{underline{2}}}{2} \
                                                                                                          &= frac{(n + 1) n (n - 1)}{3} + frac{(n + 1) n}{2} \
                                                                                                          &= frac{(2 n + 1) (n + 1) n}{6}
                                                                                                          end{align}$






                                                                                                          share|cite|improve this answer









                                                                                                          $endgroup$



                                                                                                          Yet another take. Start with the definition of falling factorial powers:



                                                                                                          $begin{align}
                                                                                                          x^{underline{r}}
                                                                                                          = x (x - 1) dotsm (x - r + 1)
                                                                                                          end{align}$



                                                                                                          so that:



                                                                                                          $begin{align}
                                                                                                          Delta n^{underline{r}}
                                                                                                          &= (n + 1)^{underline{r}} - n^{underline{r}} \
                                                                                                          &= r n^{underline{r - 1}} \
                                                                                                          sum_{0 le k < n} k^{underline{r}}
                                                                                                          &= frac{n^{underline{r + 1}}}{r + 1}
                                                                                                          end{align}$



                                                                                                          (the last one is also easy to prove by induction, or otherwise).





                                                                                                          Now note that:



                                                                                                          $begin{align}
                                                                                                          n^2
                                                                                                          = n^{underline{2}} + n^{underline{1}}
                                                                                                          end{align}$



                                                                                                          so we can write:



                                                                                                          $begin{align}
                                                                                                          sum_{0 le k le n} k^2
                                                                                                          &= sum_{0 le k < n + 1}
                                                                                                          left( k^{underline{2}} + k^{underline{1}} right) \
                                                                                                          &= frac{(n + 1)^{underline{3}}}{3}
                                                                                                          + frac{(n + 1)^{underline{2}}}{2} \
                                                                                                          &= frac{(n + 1) n (n - 1)}{3} + frac{(n + 1) n}{2} \
                                                                                                          &= frac{(2 n + 1) (n + 1) n}{6}
                                                                                                          end{align}$







                                                                                                          share|cite|improve this answer












                                                                                                          share|cite|improve this answer



                                                                                                          share|cite|improve this answer










                                                                                                          answered Oct 22 '15 at 12:35









                                                                                                          vonbrandvonbrand

                                                                                                          19.8k63058




                                                                                                          19.8k63058























                                                                                                              3












                                                                                                              $begingroup$

                                                                                                              My contribution:
                                                                                                              $$begin{align}
                                                                                                              sum_{k=1}^n k^2&=frac 14sum_{k=1}^n(2k)^2\
                                                                                                              &=frac 14sum_{k=1}^nbinom {2k}2+binom {2k+1}2\
                                                                                                              &=frac 14sum_{k=2}^{2n+1} binom k2\
                                                                                                              &=frac 14binom {2n+2}3\
                                                                                                              &=frac 14cdot frac {(2n+2)(2n+1)(2n)}{1cdot 2cdot 3}
                                                                                                              =color{lightgrey}{frac{(n+1)(2n+1)n}{1cdot 2cdot 3}}\
                                                                                                              &=frac 16n(n+1)(2n+1)quadblacksquare
                                                                                                              end{align}$$






                                                                                                              share|cite|improve this answer











                                                                                                              $endgroup$













                                                                                                              • $begingroup$
                                                                                                                Why $sum_{k=1}^n (2k)^2=sum_{k=1}^nleft(binom{2k}{2}+binom{2k+1}{2}right)$?
                                                                                                                $endgroup$
                                                                                                                – user236182
                                                                                                                Oct 21 '15 at 17:19






                                                                                                              • 1




                                                                                                                $begingroup$
                                                                                                                @user236182 - For any integer $a$, $$a^2=frac {a(a-1)}2+frac {(a+1)a}2=binom a2+binom {a+1}2$$ Putting $a=2k$ gives the result used above.
                                                                                                                $endgroup$
                                                                                                                – hypergeometric
                                                                                                                Oct 21 '15 at 23:04












                                                                                                              • $begingroup$
                                                                                                                Why $sum_{k=1}^{2n+1}binom{k}{2}=binom{2n+2}{3}$?
                                                                                                                $endgroup$
                                                                                                                – user236182
                                                                                                                Oct 21 '15 at 23:07










                                                                                                              • $begingroup$
                                                                                                                @user236182 - The following is a well-known identity: $$sum_{k=m}^Nbinom km=binom {N+1}{m+1}$$ A proof of it may be found here as a solution to a recent question. Putting $N=2n+1$ results in the identity used in the solution.
                                                                                                                $endgroup$
                                                                                                                – hypergeometric
                                                                                                                Oct 22 '15 at 14:42


















                                                                                                              3












                                                                                                              $begingroup$

                                                                                                              My contribution:
                                                                                                              $$begin{align}
                                                                                                              sum_{k=1}^n k^2&=frac 14sum_{k=1}^n(2k)^2\
                                                                                                              &=frac 14sum_{k=1}^nbinom {2k}2+binom {2k+1}2\
                                                                                                              &=frac 14sum_{k=2}^{2n+1} binom k2\
                                                                                                              &=frac 14binom {2n+2}3\
                                                                                                              &=frac 14cdot frac {(2n+2)(2n+1)(2n)}{1cdot 2cdot 3}
                                                                                                              =color{lightgrey}{frac{(n+1)(2n+1)n}{1cdot 2cdot 3}}\
                                                                                                              &=frac 16n(n+1)(2n+1)quadblacksquare
                                                                                                              end{align}$$






                                                                                                              share|cite|improve this answer











                                                                                                              $endgroup$













                                                                                                              • $begingroup$
                                                                                                                Why $sum_{k=1}^n (2k)^2=sum_{k=1}^nleft(binom{2k}{2}+binom{2k+1}{2}right)$?
                                                                                                                $endgroup$
                                                                                                                – user236182
                                                                                                                Oct 21 '15 at 17:19






                                                                                                              • 1




                                                                                                                $begingroup$
                                                                                                                @user236182 - For any integer $a$, $$a^2=frac {a(a-1)}2+frac {(a+1)a}2=binom a2+binom {a+1}2$$ Putting $a=2k$ gives the result used above.
                                                                                                                $endgroup$
                                                                                                                – hypergeometric
                                                                                                                Oct 21 '15 at 23:04












                                                                                                              • $begingroup$
                                                                                                                Why $sum_{k=1}^{2n+1}binom{k}{2}=binom{2n+2}{3}$?
                                                                                                                $endgroup$
                                                                                                                – user236182
                                                                                                                Oct 21 '15 at 23:07










                                                                                                              • $begingroup$
                                                                                                                @user236182 - The following is a well-known identity: $$sum_{k=m}^Nbinom km=binom {N+1}{m+1}$$ A proof of it may be found here as a solution to a recent question. Putting $N=2n+1$ results in the identity used in the solution.
                                                                                                                $endgroup$
                                                                                                                – hypergeometric
                                                                                                                Oct 22 '15 at 14:42
















                                                                                                              3












                                                                                                              3








                                                                                                              3





                                                                                                              $begingroup$

                                                                                                              My contribution:
                                                                                                              $$begin{align}
                                                                                                              sum_{k=1}^n k^2&=frac 14sum_{k=1}^n(2k)^2\
                                                                                                              &=frac 14sum_{k=1}^nbinom {2k}2+binom {2k+1}2\
                                                                                                              &=frac 14sum_{k=2}^{2n+1} binom k2\
                                                                                                              &=frac 14binom {2n+2}3\
                                                                                                              &=frac 14cdot frac {(2n+2)(2n+1)(2n)}{1cdot 2cdot 3}
                                                                                                              =color{lightgrey}{frac{(n+1)(2n+1)n}{1cdot 2cdot 3}}\
                                                                                                              &=frac 16n(n+1)(2n+1)quadblacksquare
                                                                                                              end{align}$$






                                                                                                              share|cite|improve this answer











                                                                                                              $endgroup$



                                                                                                              My contribution:
                                                                                                              $$begin{align}
                                                                                                              sum_{k=1}^n k^2&=frac 14sum_{k=1}^n(2k)^2\
                                                                                                              &=frac 14sum_{k=1}^nbinom {2k}2+binom {2k+1}2\
                                                                                                              &=frac 14sum_{k=2}^{2n+1} binom k2\
                                                                                                              &=frac 14binom {2n+2}3\
                                                                                                              &=frac 14cdot frac {(2n+2)(2n+1)(2n)}{1cdot 2cdot 3}
                                                                                                              =color{lightgrey}{frac{(n+1)(2n+1)n}{1cdot 2cdot 3}}\
                                                                                                              &=frac 16n(n+1)(2n+1)quadblacksquare
                                                                                                              end{align}$$







                                                                                                              share|cite|improve this answer














                                                                                                              share|cite|improve this answer



                                                                                                              share|cite|improve this answer








                                                                                                              edited Oct 22 '15 at 14:40

























                                                                                                              answered Oct 21 '15 at 16:47









                                                                                                              hypergeometrichypergeometric

                                                                                                              17.6k1758




                                                                                                              17.6k1758












                                                                                                              • $begingroup$
                                                                                                                Why $sum_{k=1}^n (2k)^2=sum_{k=1}^nleft(binom{2k}{2}+binom{2k+1}{2}right)$?
                                                                                                                $endgroup$
                                                                                                                – user236182
                                                                                                                Oct 21 '15 at 17:19






                                                                                                              • 1




                                                                                                                $begingroup$
                                                                                                                @user236182 - For any integer $a$, $$a^2=frac {a(a-1)}2+frac {(a+1)a}2=binom a2+binom {a+1}2$$ Putting $a=2k$ gives the result used above.
                                                                                                                $endgroup$
                                                                                                                – hypergeometric
                                                                                                                Oct 21 '15 at 23:04












                                                                                                              • $begingroup$
                                                                                                                Why $sum_{k=1}^{2n+1}binom{k}{2}=binom{2n+2}{3}$?
                                                                                                                $endgroup$
                                                                                                                – user236182
                                                                                                                Oct 21 '15 at 23:07










                                                                                                              • $begingroup$
                                                                                                                @user236182 - The following is a well-known identity: $$sum_{k=m}^Nbinom km=binom {N+1}{m+1}$$ A proof of it may be found here as a solution to a recent question. Putting $N=2n+1$ results in the identity used in the solution.
                                                                                                                $endgroup$
                                                                                                                – hypergeometric
                                                                                                                Oct 22 '15 at 14:42




















                                                                                                              • $begingroup$
                                                                                                                Why $sum_{k=1}^n (2k)^2=sum_{k=1}^nleft(binom{2k}{2}+binom{2k+1}{2}right)$?
                                                                                                                $endgroup$
                                                                                                                – user236182
                                                                                                                Oct 21 '15 at 17:19






                                                                                                              • 1




                                                                                                                $begingroup$
                                                                                                                @user236182 - For any integer $a$, $$a^2=frac {a(a-1)}2+frac {(a+1)a}2=binom a2+binom {a+1}2$$ Putting $a=2k$ gives the result used above.
                                                                                                                $endgroup$
                                                                                                                – hypergeometric
                                                                                                                Oct 21 '15 at 23:04












                                                                                                              • $begingroup$
                                                                                                                Why $sum_{k=1}^{2n+1}binom{k}{2}=binom{2n+2}{3}$?
                                                                                                                $endgroup$
                                                                                                                – user236182
                                                                                                                Oct 21 '15 at 23:07










                                                                                                              • $begingroup$
                                                                                                                @user236182 - The following is a well-known identity: $$sum_{k=m}^Nbinom km=binom {N+1}{m+1}$$ A proof of it may be found here as a solution to a recent question. Putting $N=2n+1$ results in the identity used in the solution.
                                                                                                                $endgroup$
                                                                                                                – hypergeometric
                                                                                                                Oct 22 '15 at 14:42


















                                                                                                              $begingroup$
                                                                                                              Why $sum_{k=1}^n (2k)^2=sum_{k=1}^nleft(binom{2k}{2}+binom{2k+1}{2}right)$?
                                                                                                              $endgroup$
                                                                                                              – user236182
                                                                                                              Oct 21 '15 at 17:19




                                                                                                              $begingroup$
                                                                                                              Why $sum_{k=1}^n (2k)^2=sum_{k=1}^nleft(binom{2k}{2}+binom{2k+1}{2}right)$?
                                                                                                              $endgroup$
                                                                                                              – user236182
                                                                                                              Oct 21 '15 at 17:19




                                                                                                              1




                                                                                                              1




                                                                                                              $begingroup$
                                                                                                              @user236182 - For any integer $a$, $$a^2=frac {a(a-1)}2+frac {(a+1)a}2=binom a2+binom {a+1}2$$ Putting $a=2k$ gives the result used above.
                                                                                                              $endgroup$
                                                                                                              – hypergeometric
                                                                                                              Oct 21 '15 at 23:04






                                                                                                              $begingroup$
                                                                                                              @user236182 - For any integer $a$, $$a^2=frac {a(a-1)}2+frac {(a+1)a}2=binom a2+binom {a+1}2$$ Putting $a=2k$ gives the result used above.
                                                                                                              $endgroup$
                                                                                                              – hypergeometric
                                                                                                              Oct 21 '15 at 23:04














                                                                                                              $begingroup$
                                                                                                              Why $sum_{k=1}^{2n+1}binom{k}{2}=binom{2n+2}{3}$?
                                                                                                              $endgroup$
                                                                                                              – user236182
                                                                                                              Oct 21 '15 at 23:07




                                                                                                              $begingroup$
                                                                                                              Why $sum_{k=1}^{2n+1}binom{k}{2}=binom{2n+2}{3}$?
                                                                                                              $endgroup$
                                                                                                              – user236182
                                                                                                              Oct 21 '15 at 23:07












                                                                                                              $begingroup$
                                                                                                              @user236182 - The following is a well-known identity: $$sum_{k=m}^Nbinom km=binom {N+1}{m+1}$$ A proof of it may be found here as a solution to a recent question. Putting $N=2n+1$ results in the identity used in the solution.
                                                                                                              $endgroup$
                                                                                                              – hypergeometric
                                                                                                              Oct 22 '15 at 14:42






                                                                                                              $begingroup$
                                                                                                              @user236182 - The following is a well-known identity: $$sum_{k=m}^Nbinom km=binom {N+1}{m+1}$$ A proof of it may be found here as a solution to a recent question. Putting $N=2n+1$ results in the identity used in the solution.
                                                                                                              $endgroup$
                                                                                                              – hypergeometric
                                                                                                              Oct 22 '15 at 14:42













                                                                                                              2












                                                                                                              $begingroup$

                                                                                                              Another way to prove this by induction goes as follows:



                                                                                                              Base case: If $n=0$, then we have $0$ on the left hand side, and $0(0+1)(2(0)+1)/6=0$ on the right.



                                                                                                              Induction step:



                                                                                                              Consider the differences $L(j+1)-L(j)$, and $R(j+1)-R(j)$ where $L(j)$ indicates that we have $j$ for $n$ on the left hand side. Well, $L(j+1)-L(j)=(j+1)^2$, and
                                                                                                              $$R(j+1)-R(j)=frac{(j+1)((j+1)+1))(2(j+1)+1)}{6} - frac{j(j+1)(2j+1)}{6}$$ which simplifies to $(j+1)^2$ also. So, the rates of change on both sides equal each other, and thus the induction step follows.






                                                                                                              share|cite|improve this answer











                                                                                                              $endgroup$


















                                                                                                                2












                                                                                                                $begingroup$

                                                                                                                Another way to prove this by induction goes as follows:



                                                                                                                Base case: If $n=0$, then we have $0$ on the left hand side, and $0(0+1)(2(0)+1)/6=0$ on the right.



                                                                                                                Induction step:



                                                                                                                Consider the differences $L(j+1)-L(j)$, and $R(j+1)-R(j)$ where $L(j)$ indicates that we have $j$ for $n$ on the left hand side. Well, $L(j+1)-L(j)=(j+1)^2$, and
                                                                                                                $$R(j+1)-R(j)=frac{(j+1)((j+1)+1))(2(j+1)+1)}{6} - frac{j(j+1)(2j+1)}{6}$$ which simplifies to $(j+1)^2$ also. So, the rates of change on both sides equal each other, and thus the induction step follows.






                                                                                                                share|cite|improve this answer











                                                                                                                $endgroup$
















                                                                                                                  2












                                                                                                                  2








                                                                                                                  2





                                                                                                                  $begingroup$

                                                                                                                  Another way to prove this by induction goes as follows:



                                                                                                                  Base case: If $n=0$, then we have $0$ on the left hand side, and $0(0+1)(2(0)+1)/6=0$ on the right.



                                                                                                                  Induction step:



                                                                                                                  Consider the differences $L(j+1)-L(j)$, and $R(j+1)-R(j)$ where $L(j)$ indicates that we have $j$ for $n$ on the left hand side. Well, $L(j+1)-L(j)=(j+1)^2$, and
                                                                                                                  $$R(j+1)-R(j)=frac{(j+1)((j+1)+1))(2(j+1)+1)}{6} - frac{j(j+1)(2j+1)}{6}$$ which simplifies to $(j+1)^2$ also. So, the rates of change on both sides equal each other, and thus the induction step follows.






                                                                                                                  share|cite|improve this answer











                                                                                                                  $endgroup$



                                                                                                                  Another way to prove this by induction goes as follows:



                                                                                                                  Base case: If $n=0$, then we have $0$ on the left hand side, and $0(0+1)(2(0)+1)/6=0$ on the right.



                                                                                                                  Induction step:



                                                                                                                  Consider the differences $L(j+1)-L(j)$, and $R(j+1)-R(j)$ where $L(j)$ indicates that we have $j$ for $n$ on the left hand side. Well, $L(j+1)-L(j)=(j+1)^2$, and
                                                                                                                  $$R(j+1)-R(j)=frac{(j+1)((j+1)+1))(2(j+1)+1)}{6} - frac{j(j+1)(2j+1)}{6}$$ which simplifies to $(j+1)^2$ also. So, the rates of change on both sides equal each other, and thus the induction step follows.







                                                                                                                  share|cite|improve this answer














                                                                                                                  share|cite|improve this answer



                                                                                                                  share|cite|improve this answer








                                                                                                                  edited Jun 28 '11 at 1:23

























                                                                                                                  answered Jun 27 '11 at 23:27









                                                                                                                  Doug SpoonwoodDoug Spoonwood

                                                                                                                  7,98512144




                                                                                                                  7,98512144























                                                                                                                      2












                                                                                                                      $begingroup$

                                                                                                                      Another take, similar to Euler's (?) proof given by @leonbloy. We know that if:



                                                                                                                      $begin{align}
                                                                                                                      A(z)
                                                                                                                      &= sum_{n ge 0} a_n z^n
                                                                                                                      end{align}$



                                                                                                                      then (writing $mathtt{D}$ for the derivative):



                                                                                                                      $begin{align}
                                                                                                                      z mathtt{D} A(z)
                                                                                                                      &= sum_{n ge 0} n a_n z^n
                                                                                                                      end{align}$



                                                                                                                      Also:



                                                                                                                      $begin{align}
                                                                                                                      frac{A(z)}{1 - z}
                                                                                                                      &= sum_{n ge 0} left( sum_{0 le k le n} a_n right) z^n \
                                                                                                                      frac{1}{1 - z}
                                                                                                                      &= sum_{n ge 0} z^n
                                                                                                                      end{align}$



                                                                                                                      This you can repeat and combine. In our case, we get that:



                                                                                                                      $begin{align}
                                                                                                                      sum_{n ge 0} n^2
                                                                                                                      &= (z mathtt{D})^2 frac{1}{1 - z} \
                                                                                                                      &= frac{z + z^2}{(1 - z)^3} \
                                                                                                                      sum_{n ge 0} left( sum_{0 le k le n} k^2 right) z^n
                                                                                                                      &= frac{z + z^2}{(1 - z)^4}
                                                                                                                      end{align}$



                                                                                                                      We are interested in the coefficient of $z^n$:



                                                                                                                      $begin{align}
                                                                                                                      [z^n] frac{z + z^2}{(1 - z)^4}
                                                                                                                      &= [z^n] frac{z}{(1 - z)^4} + [z^n] frac{z^2}{(1 - z)^4} \
                                                                                                                      &= [z^{n - 1}] (1 - z)^{-4} + [z^{n - 2}] (1 - z)^{-4} \
                                                                                                                      &= (-1)^{n - 1} binom{-4}{n - 1} + (-1)^{n - 2} binom{-4}{n - 2} \
                                                                                                                      &= binom{n - 1 + 4 - 1}{4 - 1} + binom{n - 2 + 4 - 1}{4 - 1} \
                                                                                                                      &= binom{n + 2}{3} + binom{n + 1}{3} \
                                                                                                                      &= frac{(n + 2) (n + 1) n}{3!} + frac{(n + 1) n (n - 1)}{3!} \
                                                                                                                      &= frac{(2 n + 1) (n + 1) n}{6}
                                                                                                                      end{align}$



                                                                                                                      This approach is less messy than the cited one (no horrible derivatives and then l'Hôpital thrice).






                                                                                                                      share|cite|improve this answer











                                                                                                                      $endgroup$









                                                                                                                      • 1




                                                                                                                        $begingroup$
                                                                                                                        Its a bit awfully sophisticated for this fact but nice ^^
                                                                                                                        $endgroup$
                                                                                                                        – Hexacoordinate-C
                                                                                                                        Oct 21 '15 at 16:56
















                                                                                                                      2












                                                                                                                      $begingroup$

                                                                                                                      Another take, similar to Euler's (?) proof given by @leonbloy. We know that if:



                                                                                                                      $begin{align}
                                                                                                                      A(z)
                                                                                                                      &= sum_{n ge 0} a_n z^n
                                                                                                                      end{align}$



                                                                                                                      then (writing $mathtt{D}$ for the derivative):



                                                                                                                      $begin{align}
                                                                                                                      z mathtt{D} A(z)
                                                                                                                      &= sum_{n ge 0} n a_n z^n
                                                                                                                      end{align}$



                                                                                                                      Also:



                                                                                                                      $begin{align}
                                                                                                                      frac{A(z)}{1 - z}
                                                                                                                      &= sum_{n ge 0} left( sum_{0 le k le n} a_n right) z^n \
                                                                                                                      frac{1}{1 - z}
                                                                                                                      &= sum_{n ge 0} z^n
                                                                                                                      end{align}$



                                                                                                                      This you can repeat and combine. In our case, we get that:



                                                                                                                      $begin{align}
                                                                                                                      sum_{n ge 0} n^2
                                                                                                                      &= (z mathtt{D})^2 frac{1}{1 - z} \
                                                                                                                      &= frac{z + z^2}{(1 - z)^3} \
                                                                                                                      sum_{n ge 0} left( sum_{0 le k le n} k^2 right) z^n
                                                                                                                      &= frac{z + z^2}{(1 - z)^4}
                                                                                                                      end{align}$



                                                                                                                      We are interested in the coefficient of $z^n$:



                                                                                                                      $begin{align}
                                                                                                                      [z^n] frac{z + z^2}{(1 - z)^4}
                                                                                                                      &= [z^n] frac{z}{(1 - z)^4} + [z^n] frac{z^2}{(1 - z)^4} \
                                                                                                                      &= [z^{n - 1}] (1 - z)^{-4} + [z^{n - 2}] (1 - z)^{-4} \
                                                                                                                      &= (-1)^{n - 1} binom{-4}{n - 1} + (-1)^{n - 2} binom{-4}{n - 2} \
                                                                                                                      &= binom{n - 1 + 4 - 1}{4 - 1} + binom{n - 2 + 4 - 1}{4 - 1} \
                                                                                                                      &= binom{n + 2}{3} + binom{n + 1}{3} \
                                                                                                                      &= frac{(n + 2) (n + 1) n}{3!} + frac{(n + 1) n (n - 1)}{3!} \
                                                                                                                      &= frac{(2 n + 1) (n + 1) n}{6}
                                                                                                                      end{align}$



                                                                                                                      This approach is less messy than the cited one (no horrible derivatives and then l'Hôpital thrice).






                                                                                                                      share|cite|improve this answer











                                                                                                                      $endgroup$









                                                                                                                      • 1




                                                                                                                        $begingroup$
                                                                                                                        Its a bit awfully sophisticated for this fact but nice ^^
                                                                                                                        $endgroup$
                                                                                                                        – Hexacoordinate-C
                                                                                                                        Oct 21 '15 at 16:56














                                                                                                                      2












                                                                                                                      2








                                                                                                                      2





                                                                                                                      $begingroup$

                                                                                                                      Another take, similar to Euler's (?) proof given by @leonbloy. We know that if:



                                                                                                                      $begin{align}
                                                                                                                      A(z)
                                                                                                                      &= sum_{n ge 0} a_n z^n
                                                                                                                      end{align}$



                                                                                                                      then (writing $mathtt{D}$ for the derivative):



                                                                                                                      $begin{align}
                                                                                                                      z mathtt{D} A(z)
                                                                                                                      &= sum_{n ge 0} n a_n z^n
                                                                                                                      end{align}$



                                                                                                                      Also:



                                                                                                                      $begin{align}
                                                                                                                      frac{A(z)}{1 - z}
                                                                                                                      &= sum_{n ge 0} left( sum_{0 le k le n} a_n right) z^n \
                                                                                                                      frac{1}{1 - z}
                                                                                                                      &= sum_{n ge 0} z^n
                                                                                                                      end{align}$



                                                                                                                      This you can repeat and combine. In our case, we get that:



                                                                                                                      $begin{align}
                                                                                                                      sum_{n ge 0} n^2
                                                                                                                      &= (z mathtt{D})^2 frac{1}{1 - z} \
                                                                                                                      &= frac{z + z^2}{(1 - z)^3} \
                                                                                                                      sum_{n ge 0} left( sum_{0 le k le n} k^2 right) z^n
                                                                                                                      &= frac{z + z^2}{(1 - z)^4}
                                                                                                                      end{align}$



                                                                                                                      We are interested in the coefficient of $z^n$:



                                                                                                                      $begin{align}
                                                                                                                      [z^n] frac{z + z^2}{(1 - z)^4}
                                                                                                                      &= [z^n] frac{z}{(1 - z)^4} + [z^n] frac{z^2}{(1 - z)^4} \
                                                                                                                      &= [z^{n - 1}] (1 - z)^{-4} + [z^{n - 2}] (1 - z)^{-4} \
                                                                                                                      &= (-1)^{n - 1} binom{-4}{n - 1} + (-1)^{n - 2} binom{-4}{n - 2} \
                                                                                                                      &= binom{n - 1 + 4 - 1}{4 - 1} + binom{n - 2 + 4 - 1}{4 - 1} \
                                                                                                                      &= binom{n + 2}{3} + binom{n + 1}{3} \
                                                                                                                      &= frac{(n + 2) (n + 1) n}{3!} + frac{(n + 1) n (n - 1)}{3!} \
                                                                                                                      &= frac{(2 n + 1) (n + 1) n}{6}
                                                                                                                      end{align}$



                                                                                                                      This approach is less messy than the cited one (no horrible derivatives and then l'Hôpital thrice).






                                                                                                                      share|cite|improve this answer











                                                                                                                      $endgroup$



                                                                                                                      Another take, similar to Euler's (?) proof given by @leonbloy. We know that if:



                                                                                                                      $begin{align}
                                                                                                                      A(z)
                                                                                                                      &= sum_{n ge 0} a_n z^n
                                                                                                                      end{align}$



                                                                                                                      then (writing $mathtt{D}$ for the derivative):



                                                                                                                      $begin{align}
                                                                                                                      z mathtt{D} A(z)
                                                                                                                      &= sum_{n ge 0} n a_n z^n
                                                                                                                      end{align}$



                                                                                                                      Also:



                                                                                                                      $begin{align}
                                                                                                                      frac{A(z)}{1 - z}
                                                                                                                      &= sum_{n ge 0} left( sum_{0 le k le n} a_n right) z^n \
                                                                                                                      frac{1}{1 - z}
                                                                                                                      &= sum_{n ge 0} z^n
                                                                                                                      end{align}$



                                                                                                                      This you can repeat and combine. In our case, we get that:



                                                                                                                      $begin{align}
                                                                                                                      sum_{n ge 0} n^2
                                                                                                                      &= (z mathtt{D})^2 frac{1}{1 - z} \
                                                                                                                      &= frac{z + z^2}{(1 - z)^3} \
                                                                                                                      sum_{n ge 0} left( sum_{0 le k le n} k^2 right) z^n
                                                                                                                      &= frac{z + z^2}{(1 - z)^4}
                                                                                                                      end{align}$



                                                                                                                      We are interested in the coefficient of $z^n$:



                                                                                                                      $begin{align}
                                                                                                                      [z^n] frac{z + z^2}{(1 - z)^4}
                                                                                                                      &= [z^n] frac{z}{(1 - z)^4} + [z^n] frac{z^2}{(1 - z)^4} \
                                                                                                                      &= [z^{n - 1}] (1 - z)^{-4} + [z^{n - 2}] (1 - z)^{-4} \
                                                                                                                      &= (-1)^{n - 1} binom{-4}{n - 1} + (-1)^{n - 2} binom{-4}{n - 2} \
                                                                                                                      &= binom{n - 1 + 4 - 1}{4 - 1} + binom{n - 2 + 4 - 1}{4 - 1} \
                                                                                                                      &= binom{n + 2}{3} + binom{n + 1}{3} \
                                                                                                                      &= frac{(n + 2) (n + 1) n}{3!} + frac{(n + 1) n (n - 1)}{3!} \
                                                                                                                      &= frac{(2 n + 1) (n + 1) n}{6}
                                                                                                                      end{align}$



                                                                                                                      This approach is less messy than the cited one (no horrible derivatives and then l'Hôpital thrice).







                                                                                                                      share|cite|improve this answer














                                                                                                                      share|cite|improve this answer



                                                                                                                      share|cite|improve this answer








                                                                                                                      edited Oct 21 '15 at 16:32

























                                                                                                                      answered Oct 21 '15 at 16:18









                                                                                                                      vonbrandvonbrand

                                                                                                                      19.8k63058




                                                                                                                      19.8k63058








                                                                                                                      • 1




                                                                                                                        $begingroup$
                                                                                                                        Its a bit awfully sophisticated for this fact but nice ^^
                                                                                                                        $endgroup$
                                                                                                                        – Hexacoordinate-C
                                                                                                                        Oct 21 '15 at 16:56














                                                                                                                      • 1




                                                                                                                        $begingroup$
                                                                                                                        Its a bit awfully sophisticated for this fact but nice ^^
                                                                                                                        $endgroup$
                                                                                                                        – Hexacoordinate-C
                                                                                                                        Oct 21 '15 at 16:56








                                                                                                                      1




                                                                                                                      1




                                                                                                                      $begingroup$
                                                                                                                      Its a bit awfully sophisticated for this fact but nice ^^
                                                                                                                      $endgroup$
                                                                                                                      – Hexacoordinate-C
                                                                                                                      Oct 21 '15 at 16:56




                                                                                                                      $begingroup$
                                                                                                                      Its a bit awfully sophisticated for this fact but nice ^^
                                                                                                                      $endgroup$
                                                                                                                      – Hexacoordinate-C
                                                                                                                      Oct 21 '15 at 16:56











                                                                                                                      2












                                                                                                                      $begingroup$

                                                                                                                      Another method:



                                                                                                                      $$begin{align}
                                                                                                                      sum_{k=1}^nk^2&=frac 12sum_{k=1}^n k(k+1)+(k-1)k\
                                                                                                                      &=frac 12 left[sum_{k=1}^n k(k+1)+sum_{k=1}^{n-1}k(k+1)right]\
                                                                                                                      &=color{lightgrey}{frac 12} left[ color{lightgrey}2sum_{k=1}^n binom {k+1}2+color{lightgrey}2sum_{k=1}^{n-1}binom {k+1}2right]\
                                                                                                                      &=binom {n+2}3+binom {n+1}3\
                                                                                                                      &=frac{color{blue}{(n+2)}(n+1)n}6+frac{(n+1)ncolor{blue}{(n-1)}}6\
                                                                                                                      &=frac {n(n+1)color{blue}{(2n+1)}}6quadblacksquare
                                                                                                                      end{align}$$






                                                                                                                      share|cite|improve this answer









                                                                                                                      $endgroup$


















                                                                                                                        2












                                                                                                                        $begingroup$

                                                                                                                        Another method:



                                                                                                                        $$begin{align}
                                                                                                                        sum_{k=1}^nk^2&=frac 12sum_{k=1}^n k(k+1)+(k-1)k\
                                                                                                                        &=frac 12 left[sum_{k=1}^n k(k+1)+sum_{k=1}^{n-1}k(k+1)right]\
                                                                                                                        &=color{lightgrey}{frac 12} left[ color{lightgrey}2sum_{k=1}^n binom {k+1}2+color{lightgrey}2sum_{k=1}^{n-1}binom {k+1}2right]\
                                                                                                                        &=binom {n+2}3+binom {n+1}3\
                                                                                                                        &=frac{color{blue}{(n+2)}(n+1)n}6+frac{(n+1)ncolor{blue}{(n-1)}}6\
                                                                                                                        &=frac {n(n+1)color{blue}{(2n+1)}}6quadblacksquare
                                                                                                                        end{align}$$






                                                                                                                        share|cite|improve this answer









                                                                                                                        $endgroup$
















                                                                                                                          2












                                                                                                                          2








                                                                                                                          2





                                                                                                                          $begingroup$

                                                                                                                          Another method:



                                                                                                                          $$begin{align}
                                                                                                                          sum_{k=1}^nk^2&=frac 12sum_{k=1}^n k(k+1)+(k-1)k\
                                                                                                                          &=frac 12 left[sum_{k=1}^n k(k+1)+sum_{k=1}^{n-1}k(k+1)right]\
                                                                                                                          &=color{lightgrey}{frac 12} left[ color{lightgrey}2sum_{k=1}^n binom {k+1}2+color{lightgrey}2sum_{k=1}^{n-1}binom {k+1}2right]\
                                                                                                                          &=binom {n+2}3+binom {n+1}3\
                                                                                                                          &=frac{color{blue}{(n+2)}(n+1)n}6+frac{(n+1)ncolor{blue}{(n-1)}}6\
                                                                                                                          &=frac {n(n+1)color{blue}{(2n+1)}}6quadblacksquare
                                                                                                                          end{align}$$






                                                                                                                          share|cite|improve this answer









                                                                                                                          $endgroup$



                                                                                                                          Another method:



                                                                                                                          $$begin{align}
                                                                                                                          sum_{k=1}^nk^2&=frac 12sum_{k=1}^n k(k+1)+(k-1)k\
                                                                                                                          &=frac 12 left[sum_{k=1}^n k(k+1)+sum_{k=1}^{n-1}k(k+1)right]\
                                                                                                                          &=color{lightgrey}{frac 12} left[ color{lightgrey}2sum_{k=1}^n binom {k+1}2+color{lightgrey}2sum_{k=1}^{n-1}binom {k+1}2right]\
                                                                                                                          &=binom {n+2}3+binom {n+1}3\
                                                                                                                          &=frac{color{blue}{(n+2)}(n+1)n}6+frac{(n+1)ncolor{blue}{(n-1)}}6\
                                                                                                                          &=frac {n(n+1)color{blue}{(2n+1)}}6quadblacksquare
                                                                                                                          end{align}$$







                                                                                                                          share|cite|improve this answer












                                                                                                                          share|cite|improve this answer



                                                                                                                          share|cite|improve this answer










                                                                                                                          answered Oct 22 '15 at 15:32









                                                                                                                          hypergeometrichypergeometric

                                                                                                                          17.6k1758




                                                                                                                          17.6k1758























                                                                                                                              2












                                                                                                                              $begingroup$

                                                                                                                              Here, we present an approach that uses only the sum of the arithmetic progression $sum_{k=1}^nk=frac12n(n+1)$.



                                                                                                                              Here, we note that $sum_{j=1}^k(1)=k$. Then, we can write



                                                                                                                              $$begin{align}
                                                                                                                              sum_{k=1}^nk^2&=sum_{k=1}^nksum_{j=1}^k(1)\\
                                                                                                                              &=sum_{j=1}^nsum_{k=j}^n,k\\
                                                                                                                              &=frac12sum_{j=1}^n(n+1-j)(j+n)\\
                                                                                                                              &=frac12sum_{j=1}^nleft(n(n+1)+j-j^2right)\\
                                                                                                                              &=frac12n^2(n+1)+frac14n(n+1)-frac12sum_{j=1}^nj^2\\
                                                                                                                              frac32sum_{k=1}^nk^2&=frac{(2n+1)n(n+1)}{4}\\
                                                                                                                              sum_{k=1}^nk^2&=frac{(2n+1)n(n+1)}{6}
                                                                                                                              end{align}$$






                                                                                                                              share|cite|improve this answer









                                                                                                                              $endgroup$


















                                                                                                                                2












                                                                                                                                $begingroup$

                                                                                                                                Here, we present an approach that uses only the sum of the arithmetic progression $sum_{k=1}^nk=frac12n(n+1)$.



                                                                                                                                Here, we note that $sum_{j=1}^k(1)=k$. Then, we can write



                                                                                                                                $$begin{align}
                                                                                                                                sum_{k=1}^nk^2&=sum_{k=1}^nksum_{j=1}^k(1)\\
                                                                                                                                &=sum_{j=1}^nsum_{k=j}^n,k\\
                                                                                                                                &=frac12sum_{j=1}^n(n+1-j)(j+n)\\
                                                                                                                                &=frac12sum_{j=1}^nleft(n(n+1)+j-j^2right)\\
                                                                                                                                &=frac12n^2(n+1)+frac14n(n+1)-frac12sum_{j=1}^nj^2\\
                                                                                                                                frac32sum_{k=1}^nk^2&=frac{(2n+1)n(n+1)}{4}\\
                                                                                                                                sum_{k=1}^nk^2&=frac{(2n+1)n(n+1)}{6}
                                                                                                                                end{align}$$






                                                                                                                                share|cite|improve this answer









                                                                                                                                $endgroup$
















                                                                                                                                  2












                                                                                                                                  2








                                                                                                                                  2





                                                                                                                                  $begingroup$

                                                                                                                                  Here, we present an approach that uses only the sum of the arithmetic progression $sum_{k=1}^nk=frac12n(n+1)$.



                                                                                                                                  Here, we note that $sum_{j=1}^k(1)=k$. Then, we can write



                                                                                                                                  $$begin{align}
                                                                                                                                  sum_{k=1}^nk^2&=sum_{k=1}^nksum_{j=1}^k(1)\\
                                                                                                                                  &=sum_{j=1}^nsum_{k=j}^n,k\\
                                                                                                                                  &=frac12sum_{j=1}^n(n+1-j)(j+n)\\
                                                                                                                                  &=frac12sum_{j=1}^nleft(n(n+1)+j-j^2right)\\
                                                                                                                                  &=frac12n^2(n+1)+frac14n(n+1)-frac12sum_{j=1}^nj^2\\
                                                                                                                                  frac32sum_{k=1}^nk^2&=frac{(2n+1)n(n+1)}{4}\\
                                                                                                                                  sum_{k=1}^nk^2&=frac{(2n+1)n(n+1)}{6}
                                                                                                                                  end{align}$$






                                                                                                                                  share|cite|improve this answer









                                                                                                                                  $endgroup$



                                                                                                                                  Here, we present an approach that uses only the sum of the arithmetic progression $sum_{k=1}^nk=frac12n(n+1)$.



                                                                                                                                  Here, we note that $sum_{j=1}^k(1)=k$. Then, we can write



                                                                                                                                  $$begin{align}
                                                                                                                                  sum_{k=1}^nk^2&=sum_{k=1}^nksum_{j=1}^k(1)\\
                                                                                                                                  &=sum_{j=1}^nsum_{k=j}^n,k\\
                                                                                                                                  &=frac12sum_{j=1}^n(n+1-j)(j+n)\\
                                                                                                                                  &=frac12sum_{j=1}^nleft(n(n+1)+j-j^2right)\\
                                                                                                                                  &=frac12n^2(n+1)+frac14n(n+1)-frac12sum_{j=1}^nj^2\\
                                                                                                                                  frac32sum_{k=1}^nk^2&=frac{(2n+1)n(n+1)}{4}\\
                                                                                                                                  sum_{k=1}^nk^2&=frac{(2n+1)n(n+1)}{6}
                                                                                                                                  end{align}$$







                                                                                                                                  share|cite|improve this answer












                                                                                                                                  share|cite|improve this answer



                                                                                                                                  share|cite|improve this answer










                                                                                                                                  answered Mar 3 '16 at 16:44









                                                                                                                                  Mark ViolaMark Viola

                                                                                                                                  131k1275171




                                                                                                                                  131k1275171























                                                                                                                                      2












                                                                                                                                      $begingroup$

                                                                                                                                      A High School Proof:
                                                                                                                                      $$S_n = 1^2 + 2^2 + 3^2 +dots+ n^2$$



                                                                                                                                      We know,



                                                                                                                                      $$r^3 - 3r^2 + 3r - 1 = (r-1)^3 $$



                                                                                                                                      $$r^3 - (r-1)^3 = 3r^2 - 3r + 1$$



                                                                                                                                      When $r=1, 2, 3,dots, n$



                                                                                                                                      $$1^3 - 0^3 = 3*1^2 - 3*1 + 1qquad(1)$$



                                                                                                                                      $$2^3 - 1^3 = 3*2^2 - 3*2 + 1qquad(2)$$



                                                                                                                                      $$3^3 - 2^3 = 3*3^2 - 3*3 + 1qquad(3)$$



                                                                                                                                      $$dotsdotsdotsdotsdotsdotsdotsdotsdots$$



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



                                                                                                                                      By summing all the equations (from 1 to n) we get,



                                                                                                                                      $$n^3 - 0^3 = 3(1^2 + 2^2 + 3^2 +dots+ n^2) - 3(1+2+3+dots+n) + (1+1+1+dots)$$



                                                                                                                                      $$n^3 = 3S_n - 3frac{n(n+1)}{2} + n$$



                                                                                                                                      begin{align}
                                                                                                                                      3S_n & = n^3 + frac{3n(n+1)}{2} - n\
                                                                                                                                      & = frac{2n^3 + 3n^2 + 3n - 2n}{2}\
                                                                                                                                      & = frac{2n^3 + 3n^2 + n}{2}\
                                                                                                                                      & = frac{n(2n^2 + 3n + 1)}{2}\
                                                                                                                                      & = frac{n(2n^2 + 2n + n + 1)}{2}\
                                                                                                                                      & = frac{n{2n(n+1)+1(n+1)}}{2}\
                                                                                                                                      & = frac{n(n+1)(2n+1)}{2}\
                                                                                                                                      end{align}



                                                                                                                                      $$therefore S_n = frac{n(n+1)(2n+1)}{6}$$






                                                                                                                                      share|cite|improve this answer









                                                                                                                                      $endgroup$


















                                                                                                                                        2












                                                                                                                                        $begingroup$

                                                                                                                                        A High School Proof:
                                                                                                                                        $$S_n = 1^2 + 2^2 + 3^2 +dots+ n^2$$



                                                                                                                                        We know,



                                                                                                                                        $$r^3 - 3r^2 + 3r - 1 = (r-1)^3 $$



                                                                                                                                        $$r^3 - (r-1)^3 = 3r^2 - 3r + 1$$



                                                                                                                                        When $r=1, 2, 3,dots, n$



                                                                                                                                        $$1^3 - 0^3 = 3*1^2 - 3*1 + 1qquad(1)$$



                                                                                                                                        $$2^3 - 1^3 = 3*2^2 - 3*2 + 1qquad(2)$$



                                                                                                                                        $$3^3 - 2^3 = 3*3^2 - 3*3 + 1qquad(3)$$



                                                                                                                                        $$dotsdotsdotsdotsdotsdotsdotsdotsdots$$



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



                                                                                                                                        By summing all the equations (from 1 to n) we get,



                                                                                                                                        $$n^3 - 0^3 = 3(1^2 + 2^2 + 3^2 +dots+ n^2) - 3(1+2+3+dots+n) + (1+1+1+dots)$$



                                                                                                                                        $$n^3 = 3S_n - 3frac{n(n+1)}{2} + n$$



                                                                                                                                        begin{align}
                                                                                                                                        3S_n & = n^3 + frac{3n(n+1)}{2} - n\
                                                                                                                                        & = frac{2n^3 + 3n^2 + 3n - 2n}{2}\
                                                                                                                                        & = frac{2n^3 + 3n^2 + n}{2}\
                                                                                                                                        & = frac{n(2n^2 + 3n + 1)}{2}\
                                                                                                                                        & = frac{n(2n^2 + 2n + n + 1)}{2}\
                                                                                                                                        & = frac{n{2n(n+1)+1(n+1)}}{2}\
                                                                                                                                        & = frac{n(n+1)(2n+1)}{2}\
                                                                                                                                        end{align}



                                                                                                                                        $$therefore S_n = frac{n(n+1)(2n+1)}{6}$$






                                                                                                                                        share|cite|improve this answer









                                                                                                                                        $endgroup$
















                                                                                                                                          2












                                                                                                                                          2








                                                                                                                                          2





                                                                                                                                          $begingroup$

                                                                                                                                          A High School Proof:
                                                                                                                                          $$S_n = 1^2 + 2^2 + 3^2 +dots+ n^2$$



                                                                                                                                          We know,



                                                                                                                                          $$r^3 - 3r^2 + 3r - 1 = (r-1)^3 $$



                                                                                                                                          $$r^3 - (r-1)^3 = 3r^2 - 3r + 1$$



                                                                                                                                          When $r=1, 2, 3,dots, n$



                                                                                                                                          $$1^3 - 0^3 = 3*1^2 - 3*1 + 1qquad(1)$$



                                                                                                                                          $$2^3 - 1^3 = 3*2^2 - 3*2 + 1qquad(2)$$



                                                                                                                                          $$3^3 - 2^3 = 3*3^2 - 3*3 + 1qquad(3)$$



                                                                                                                                          $$dotsdotsdotsdotsdotsdotsdotsdotsdots$$



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



                                                                                                                                          By summing all the equations (from 1 to n) we get,



                                                                                                                                          $$n^3 - 0^3 = 3(1^2 + 2^2 + 3^2 +dots+ n^2) - 3(1+2+3+dots+n) + (1+1+1+dots)$$



                                                                                                                                          $$n^3 = 3S_n - 3frac{n(n+1)}{2} + n$$



                                                                                                                                          begin{align}
                                                                                                                                          3S_n & = n^3 + frac{3n(n+1)}{2} - n\
                                                                                                                                          & = frac{2n^3 + 3n^2 + 3n - 2n}{2}\
                                                                                                                                          & = frac{2n^3 + 3n^2 + n}{2}\
                                                                                                                                          & = frac{n(2n^2 + 3n + 1)}{2}\
                                                                                                                                          & = frac{n(2n^2 + 2n + n + 1)}{2}\
                                                                                                                                          & = frac{n{2n(n+1)+1(n+1)}}{2}\
                                                                                                                                          & = frac{n(n+1)(2n+1)}{2}\
                                                                                                                                          end{align}



                                                                                                                                          $$therefore S_n = frac{n(n+1)(2n+1)}{6}$$






                                                                                                                                          share|cite|improve this answer









                                                                                                                                          $endgroup$



                                                                                                                                          A High School Proof:
                                                                                                                                          $$S_n = 1^2 + 2^2 + 3^2 +dots+ n^2$$



                                                                                                                                          We know,



                                                                                                                                          $$r^3 - 3r^2 + 3r - 1 = (r-1)^3 $$



                                                                                                                                          $$r^3 - (r-1)^3 = 3r^2 - 3r + 1$$



                                                                                                                                          When $r=1, 2, 3,dots, n$



                                                                                                                                          $$1^3 - 0^3 = 3*1^2 - 3*1 + 1qquad(1)$$



                                                                                                                                          $$2^3 - 1^3 = 3*2^2 - 3*2 + 1qquad(2)$$



                                                                                                                                          $$3^3 - 2^3 = 3*3^2 - 3*3 + 1qquad(3)$$



                                                                                                                                          $$dotsdotsdotsdotsdotsdotsdotsdotsdots$$



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



                                                                                                                                          By summing all the equations (from 1 to n) we get,



                                                                                                                                          $$n^3 - 0^3 = 3(1^2 + 2^2 + 3^2 +dots+ n^2) - 3(1+2+3+dots+n) + (1+1+1+dots)$$



                                                                                                                                          $$n^3 = 3S_n - 3frac{n(n+1)}{2} + n$$



                                                                                                                                          begin{align}
                                                                                                                                          3S_n & = n^3 + frac{3n(n+1)}{2} - n\
                                                                                                                                          & = frac{2n^3 + 3n^2 + 3n - 2n}{2}\
                                                                                                                                          & = frac{2n^3 + 3n^2 + n}{2}\
                                                                                                                                          & = frac{n(2n^2 + 3n + 1)}{2}\
                                                                                                                                          & = frac{n(2n^2 + 2n + n + 1)}{2}\
                                                                                                                                          & = frac{n{2n(n+1)+1(n+1)}}{2}\
                                                                                                                                          & = frac{n(n+1)(2n+1)}{2}\
                                                                                                                                          end{align}



                                                                                                                                          $$therefore S_n = frac{n(n+1)(2n+1)}{6}$$







                                                                                                                                          share|cite|improve this answer












                                                                                                                                          share|cite|improve this answer



                                                                                                                                          share|cite|improve this answer










                                                                                                                                          answered Mar 24 '17 at 11:51









                                                                                                                                          SakirSakir

                                                                                                                                          211




                                                                                                                                          211























                                                                                                                                              0












                                                                                                                                              $begingroup$

                                                                                                                                              For proof by induction; these are the $color{green}{mathrm{three}}$ steps to carry out:



                                                                                                                                              Step 1: Basis Case: For $i=1$: $$sum^{i=k}_{i=1} i^2=frac{1(1+1)(2times 1+1)}{6}= frac{2times 3}{6}=1$$ So statement holds for $i=1$.



                                                                                                                                              Step 2: Inductive Assumption: Assume statement is true for $i=k$:



                                                                                                                                              $$sum^{i=k}_{i=1} i^2=frac{k(k+1)(2k+1)}{6} $$



                                                                                                                                              Step 3: Prove Statement holds for $i=k+1$. You need to prove that for $i=k+1$: $$sum^{i=k+1}_{i=1} i^2=color{blue}{frac{(k+1)(k+2)(2k+3)}{6}}$$



                                                                                                                                              To do this you cannot use: $$sum^{i=k}_{i=n} i^2=color{red}{frac{n(n+1)(2n+1)}{6}} $$ as this is what you are trying to prove.



                                                                                                                                              So what you do instead is notice that:
                                                                                                                                              $$sum^{i=k+1}_{i=1} i^2= underbrace{frac{k(k+1)(2k+1)}{6}}_{text{sum of k terms}} + underbrace{(k+1)^2}_{text{(k+1)th term}}$$
                                                                                                                                              $$sum^{i=k+1}_{i=1} i^2= frac{k(k+1)(2k+1)}{6}+frac{6(k+1)^2}{6}$$
                                                                                                                                              $$sum^{i=k+1}_{i=1} i^2= frac{(k+1)left(k(2k+1)+6(k+1)right)}{6}$$
                                                                                                                                              $$sum^{i=k+1}_{i=1} i^2= frac{(k+1)(2k^2+color{green}{7k}+6)}{6}=frac{(k+1)(2k^2+color{green}{4k+3k}+6)}{6}=frac{(k+1)left(2k(k+2)+3(k+2)right)}{6}=color{blue}{frac{(k+1)(k+2)(2k+3)}{6}}quad forall space k in mathbb{N}$$



                                                                                                                                              Which is the relation we set out to prove. So the method is to substitute $i=k+1$ into the formula you are trying to prove and then use the inductive assumption to recover the $color{blue}{mathrm{blue}}$ equation at the end.






                                                                                                                                              share|cite|improve this answer











                                                                                                                                              $endgroup$


















                                                                                                                                                0












                                                                                                                                                $begingroup$

                                                                                                                                                For proof by induction; these are the $color{green}{mathrm{three}}$ steps to carry out:



                                                                                                                                                Step 1: Basis Case: For $i=1$: $$sum^{i=k}_{i=1} i^2=frac{1(1+1)(2times 1+1)}{6}= frac{2times 3}{6}=1$$ So statement holds for $i=1$.



                                                                                                                                                Step 2: Inductive Assumption: Assume statement is true for $i=k$:



                                                                                                                                                $$sum^{i=k}_{i=1} i^2=frac{k(k+1)(2k+1)}{6} $$



                                                                                                                                                Step 3: Prove Statement holds for $i=k+1$. You need to prove that for $i=k+1$: $$sum^{i=k+1}_{i=1} i^2=color{blue}{frac{(k+1)(k+2)(2k+3)}{6}}$$



                                                                                                                                                To do this you cannot use: $$sum^{i=k}_{i=n} i^2=color{red}{frac{n(n+1)(2n+1)}{6}} $$ as this is what you are trying to prove.



                                                                                                                                                So what you do instead is notice that:
                                                                                                                                                $$sum^{i=k+1}_{i=1} i^2= underbrace{frac{k(k+1)(2k+1)}{6}}_{text{sum of k terms}} + underbrace{(k+1)^2}_{text{(k+1)th term}}$$
                                                                                                                                                $$sum^{i=k+1}_{i=1} i^2= frac{k(k+1)(2k+1)}{6}+frac{6(k+1)^2}{6}$$
                                                                                                                                                $$sum^{i=k+1}_{i=1} i^2= frac{(k+1)left(k(2k+1)+6(k+1)right)}{6}$$
                                                                                                                                                $$sum^{i=k+1}_{i=1} i^2= frac{(k+1)(2k^2+color{green}{7k}+6)}{6}=frac{(k+1)(2k^2+color{green}{4k+3k}+6)}{6}=frac{(k+1)left(2k(k+2)+3(k+2)right)}{6}=color{blue}{frac{(k+1)(k+2)(2k+3)}{6}}quad forall space k in mathbb{N}$$



                                                                                                                                                Which is the relation we set out to prove. So the method is to substitute $i=k+1$ into the formula you are trying to prove and then use the inductive assumption to recover the $color{blue}{mathrm{blue}}$ equation at the end.






                                                                                                                                                share|cite|improve this answer











                                                                                                                                                $endgroup$
















                                                                                                                                                  0












                                                                                                                                                  0








                                                                                                                                                  0





                                                                                                                                                  $begingroup$

                                                                                                                                                  For proof by induction; these are the $color{green}{mathrm{three}}$ steps to carry out:



                                                                                                                                                  Step 1: Basis Case: For $i=1$: $$sum^{i=k}_{i=1} i^2=frac{1(1+1)(2times 1+1)}{6}= frac{2times 3}{6}=1$$ So statement holds for $i=1$.



                                                                                                                                                  Step 2: Inductive Assumption: Assume statement is true for $i=k$:



                                                                                                                                                  $$sum^{i=k}_{i=1} i^2=frac{k(k+1)(2k+1)}{6} $$



                                                                                                                                                  Step 3: Prove Statement holds for $i=k+1$. You need to prove that for $i=k+1$: $$sum^{i=k+1}_{i=1} i^2=color{blue}{frac{(k+1)(k+2)(2k+3)}{6}}$$



                                                                                                                                                  To do this you cannot use: $$sum^{i=k}_{i=n} i^2=color{red}{frac{n(n+1)(2n+1)}{6}} $$ as this is what you are trying to prove.



                                                                                                                                                  So what you do instead is notice that:
                                                                                                                                                  $$sum^{i=k+1}_{i=1} i^2= underbrace{frac{k(k+1)(2k+1)}{6}}_{text{sum of k terms}} + underbrace{(k+1)^2}_{text{(k+1)th term}}$$
                                                                                                                                                  $$sum^{i=k+1}_{i=1} i^2= frac{k(k+1)(2k+1)}{6}+frac{6(k+1)^2}{6}$$
                                                                                                                                                  $$sum^{i=k+1}_{i=1} i^2= frac{(k+1)left(k(2k+1)+6(k+1)right)}{6}$$
                                                                                                                                                  $$sum^{i=k+1}_{i=1} i^2= frac{(k+1)(2k^2+color{green}{7k}+6)}{6}=frac{(k+1)(2k^2+color{green}{4k+3k}+6)}{6}=frac{(k+1)left(2k(k+2)+3(k+2)right)}{6}=color{blue}{frac{(k+1)(k+2)(2k+3)}{6}}quad forall space k in mathbb{N}$$



                                                                                                                                                  Which is the relation we set out to prove. So the method is to substitute $i=k+1$ into the formula you are trying to prove and then use the inductive assumption to recover the $color{blue}{mathrm{blue}}$ equation at the end.






                                                                                                                                                  share|cite|improve this answer











                                                                                                                                                  $endgroup$



                                                                                                                                                  For proof by induction; these are the $color{green}{mathrm{three}}$ steps to carry out:



                                                                                                                                                  Step 1: Basis Case: For $i=1$: $$sum^{i=k}_{i=1} i^2=frac{1(1+1)(2times 1+1)}{6}= frac{2times 3}{6}=1$$ So statement holds for $i=1$.



                                                                                                                                                  Step 2: Inductive Assumption: Assume statement is true for $i=k$:



                                                                                                                                                  $$sum^{i=k}_{i=1} i^2=frac{k(k+1)(2k+1)}{6} $$



                                                                                                                                                  Step 3: Prove Statement holds for $i=k+1$. You need to prove that for $i=k+1$: $$sum^{i=k+1}_{i=1} i^2=color{blue}{frac{(k+1)(k+2)(2k+3)}{6}}$$



                                                                                                                                                  To do this you cannot use: $$sum^{i=k}_{i=n} i^2=color{red}{frac{n(n+1)(2n+1)}{6}} $$ as this is what you are trying to prove.



                                                                                                                                                  So what you do instead is notice that:
                                                                                                                                                  $$sum^{i=k+1}_{i=1} i^2= underbrace{frac{k(k+1)(2k+1)}{6}}_{text{sum of k terms}} + underbrace{(k+1)^2}_{text{(k+1)th term}}$$
                                                                                                                                                  $$sum^{i=k+1}_{i=1} i^2= frac{k(k+1)(2k+1)}{6}+frac{6(k+1)^2}{6}$$
                                                                                                                                                  $$sum^{i=k+1}_{i=1} i^2= frac{(k+1)left(k(2k+1)+6(k+1)right)}{6}$$
                                                                                                                                                  $$sum^{i=k+1}_{i=1} i^2= frac{(k+1)(2k^2+color{green}{7k}+6)}{6}=frac{(k+1)(2k^2+color{green}{4k+3k}+6)}{6}=frac{(k+1)left(2k(k+2)+3(k+2)right)}{6}=color{blue}{frac{(k+1)(k+2)(2k+3)}{6}}quad forall space k in mathbb{N}$$



                                                                                                                                                  Which is the relation we set out to prove. So the method is to substitute $i=k+1$ into the formula you are trying to prove and then use the inductive assumption to recover the $color{blue}{mathrm{blue}}$ equation at the end.







                                                                                                                                                  share|cite|improve this answer














                                                                                                                                                  share|cite|improve this answer



                                                                                                                                                  share|cite|improve this answer








                                                                                                                                                  edited Nov 16 '15 at 12:26

























                                                                                                                                                  answered Oct 31 '15 at 17:36









                                                                                                                                                  BLAZEBLAZE

                                                                                                                                                  6,076112755




                                                                                                                                                  6,076112755























                                                                                                                                                      0












                                                                                                                                                      $begingroup$

                                                                                                                                                      Here is a sketch with calculus.



                                                                                                                                                      $f(x) = x^2$ is a strictly monotonously increasing function. The sum is an upper Riemann sum of width 1 of this function. But if we shift it down one step we get a lower Riemann sum of width 1. The difference in integral is $$int_{n-1}^n f(x)dx - int_0^1 f(x)dx = n^3/3 - (n-3)^3/3 - 1 = n^2-3n-4$$





                                                                                                                                                      This is not quite $n^2$, but we can now turn the question into asking "if we had an offset in the integration, say $+alpha$ on each "step", what $alpha$ should we select to get as close to $n^2$ as possible?"



                                                                                                                                                      This is not a full answer, but intends on helping how to think to try and solve problems.






                                                                                                                                                      share|cite|improve this answer









                                                                                                                                                      $endgroup$


















                                                                                                                                                        0












                                                                                                                                                        $begingroup$

                                                                                                                                                        Here is a sketch with calculus.



                                                                                                                                                        $f(x) = x^2$ is a strictly monotonously increasing function. The sum is an upper Riemann sum of width 1 of this function. But if we shift it down one step we get a lower Riemann sum of width 1. The difference in integral is $$int_{n-1}^n f(x)dx - int_0^1 f(x)dx = n^3/3 - (n-3)^3/3 - 1 = n^2-3n-4$$





                                                                                                                                                        This is not quite $n^2$, but we can now turn the question into asking "if we had an offset in the integration, say $+alpha$ on each "step", what $alpha$ should we select to get as close to $n^2$ as possible?"



                                                                                                                                                        This is not a full answer, but intends on helping how to think to try and solve problems.






                                                                                                                                                        share|cite|improve this answer









                                                                                                                                                        $endgroup$
















                                                                                                                                                          0












                                                                                                                                                          0








                                                                                                                                                          0





                                                                                                                                                          $begingroup$

                                                                                                                                                          Here is a sketch with calculus.



                                                                                                                                                          $f(x) = x^2$ is a strictly monotonously increasing function. The sum is an upper Riemann sum of width 1 of this function. But if we shift it down one step we get a lower Riemann sum of width 1. The difference in integral is $$int_{n-1}^n f(x)dx - int_0^1 f(x)dx = n^3/3 - (n-3)^3/3 - 1 = n^2-3n-4$$





                                                                                                                                                          This is not quite $n^2$, but we can now turn the question into asking "if we had an offset in the integration, say $+alpha$ on each "step", what $alpha$ should we select to get as close to $n^2$ as possible?"



                                                                                                                                                          This is not a full answer, but intends on helping how to think to try and solve problems.






                                                                                                                                                          share|cite|improve this answer









                                                                                                                                                          $endgroup$



                                                                                                                                                          Here is a sketch with calculus.



                                                                                                                                                          $f(x) = x^2$ is a strictly monotonously increasing function. The sum is an upper Riemann sum of width 1 of this function. But if we shift it down one step we get a lower Riemann sum of width 1. The difference in integral is $$int_{n-1}^n f(x)dx - int_0^1 f(x)dx = n^3/3 - (n-3)^3/3 - 1 = n^2-3n-4$$





                                                                                                                                                          This is not quite $n^2$, but we can now turn the question into asking "if we had an offset in the integration, say $+alpha$ on each "step", what $alpha$ should we select to get as close to $n^2$ as possible?"



                                                                                                                                                          This is not a full answer, but intends on helping how to think to try and solve problems.







                                                                                                                                                          share|cite|improve this answer












                                                                                                                                                          share|cite|improve this answer



                                                                                                                                                          share|cite|improve this answer










                                                                                                                                                          answered Mar 24 '17 at 11:50









                                                                                                                                                          mathreadlermathreadler

                                                                                                                                                          14.8k72160




                                                                                                                                                          14.8k72160























                                                                                                                                                              0












                                                                                                                                                              $begingroup$

                                                                                                                                                              Firstly, calculate the sum $S=sum_{k=1}^n k(k+1)$ which is:



                                                                                                                                                              $S=1cdot 2+2cdot 3+ cdots +n(n+1)$,



                                                                                                                                                              multiplying $S$ by 3
                                                                                                                                                              we get:



                                                                                                                                                              $3S=1cdot 2cdot 3+2cdot 3cdot (4-1)+3cdot 4cdot (5-2)+ cdots +ncdot (n+1)cdot (n+2-(n-1))$



                                                                                                                                                              $3S=1 · 2 · 3 + 2 · 3 · 4 − 1 · 2 · 3 + 3 · 4 · 5 − 2 · 3 · 4 + · · ·
                                                                                                                                                              + n(n + 1)(n + 2) − (n − 1)n(n + 1)$



                                                                                                                                                              This telescoping series collapses to yield:



                                                                                                                                                              $$3S=n(n+1)(n+2)$$



                                                                                                                                                              $$S=frac{n(n+1)(n+2)}{3}$$



                                                                                                                                                              On the other side we have:



                                                                                                                                                              begin{alignat*}{2}
                                                                                                                                                              &sum_{k=1}^n k(k+1)&&=sum_{k=1}^n k^2+k \
                                                                                                                                                              & &&=sum_{k=1}^n k^2+sum_{k=1}^n k \
                                                                                                                                                              &frac{n(n+1)(n+2)}{3}&&=sum_{k=1}^n k^2+frac{n(n+1)}{2} \
                                                                                                                                                              &sum_{k=1}^n k^2&&=frac{n(n+1)(n+2)}{3}-frac{n(n+1)}{2} \
                                                                                                                                                              &sum_{k=1}^n k^2&&=frac{n(n+1)(2n+1)}{6}
                                                                                                                                                              end{alignat*}






                                                                                                                                                              share|cite|improve this answer











                                                                                                                                                              $endgroup$


















                                                                                                                                                                0












                                                                                                                                                                $begingroup$

                                                                                                                                                                Firstly, calculate the sum $S=sum_{k=1}^n k(k+1)$ which is:



                                                                                                                                                                $S=1cdot 2+2cdot 3+ cdots +n(n+1)$,



                                                                                                                                                                multiplying $S$ by 3
                                                                                                                                                                we get:



                                                                                                                                                                $3S=1cdot 2cdot 3+2cdot 3cdot (4-1)+3cdot 4cdot (5-2)+ cdots +ncdot (n+1)cdot (n+2-(n-1))$



                                                                                                                                                                $3S=1 · 2 · 3 + 2 · 3 · 4 − 1 · 2 · 3 + 3 · 4 · 5 − 2 · 3 · 4 + · · ·
                                                                                                                                                                + n(n + 1)(n + 2) − (n − 1)n(n + 1)$



                                                                                                                                                                This telescoping series collapses to yield:



                                                                                                                                                                $$3S=n(n+1)(n+2)$$



                                                                                                                                                                $$S=frac{n(n+1)(n+2)}{3}$$



                                                                                                                                                                On the other side we have:



                                                                                                                                                                begin{alignat*}{2}
                                                                                                                                                                &sum_{k=1}^n k(k+1)&&=sum_{k=1}^n k^2+k \
                                                                                                                                                                & &&=sum_{k=1}^n k^2+sum_{k=1}^n k \
                                                                                                                                                                &frac{n(n+1)(n+2)}{3}&&=sum_{k=1}^n k^2+frac{n(n+1)}{2} \
                                                                                                                                                                &sum_{k=1}^n k^2&&=frac{n(n+1)(n+2)}{3}-frac{n(n+1)}{2} \
                                                                                                                                                                &sum_{k=1}^n k^2&&=frac{n(n+1)(2n+1)}{6}
                                                                                                                                                                end{alignat*}






                                                                                                                                                                share|cite|improve this answer











                                                                                                                                                                $endgroup$
















                                                                                                                                                                  0












                                                                                                                                                                  0








                                                                                                                                                                  0





                                                                                                                                                                  $begingroup$

                                                                                                                                                                  Firstly, calculate the sum $S=sum_{k=1}^n k(k+1)$ which is:



                                                                                                                                                                  $S=1cdot 2+2cdot 3+ cdots +n(n+1)$,



                                                                                                                                                                  multiplying $S$ by 3
                                                                                                                                                                  we get:



                                                                                                                                                                  $3S=1cdot 2cdot 3+2cdot 3cdot (4-1)+3cdot 4cdot (5-2)+ cdots +ncdot (n+1)cdot (n+2-(n-1))$



                                                                                                                                                                  $3S=1 · 2 · 3 + 2 · 3 · 4 − 1 · 2 · 3 + 3 · 4 · 5 − 2 · 3 · 4 + · · ·
                                                                                                                                                                  + n(n + 1)(n + 2) − (n − 1)n(n + 1)$



                                                                                                                                                                  This telescoping series collapses to yield:



                                                                                                                                                                  $$3S=n(n+1)(n+2)$$



                                                                                                                                                                  $$S=frac{n(n+1)(n+2)}{3}$$



                                                                                                                                                                  On the other side we have:



                                                                                                                                                                  begin{alignat*}{2}
                                                                                                                                                                  &sum_{k=1}^n k(k+1)&&=sum_{k=1}^n k^2+k \
                                                                                                                                                                  & &&=sum_{k=1}^n k^2+sum_{k=1}^n k \
                                                                                                                                                                  &frac{n(n+1)(n+2)}{3}&&=sum_{k=1}^n k^2+frac{n(n+1)}{2} \
                                                                                                                                                                  &sum_{k=1}^n k^2&&=frac{n(n+1)(n+2)}{3}-frac{n(n+1)}{2} \
                                                                                                                                                                  &sum_{k=1}^n k^2&&=frac{n(n+1)(2n+1)}{6}
                                                                                                                                                                  end{alignat*}






                                                                                                                                                                  share|cite|improve this answer











                                                                                                                                                                  $endgroup$



                                                                                                                                                                  Firstly, calculate the sum $S=sum_{k=1}^n k(k+1)$ which is:



                                                                                                                                                                  $S=1cdot 2+2cdot 3+ cdots +n(n+1)$,



                                                                                                                                                                  multiplying $S$ by 3
                                                                                                                                                                  we get:



                                                                                                                                                                  $3S=1cdot 2cdot 3+2cdot 3cdot (4-1)+3cdot 4cdot (5-2)+ cdots +ncdot (n+1)cdot (n+2-(n-1))$



                                                                                                                                                                  $3S=1 · 2 · 3 + 2 · 3 · 4 − 1 · 2 · 3 + 3 · 4 · 5 − 2 · 3 · 4 + · · ·
                                                                                                                                                                  + n(n + 1)(n + 2) − (n − 1)n(n + 1)$



                                                                                                                                                                  This telescoping series collapses to yield:



                                                                                                                                                                  $$3S=n(n+1)(n+2)$$



                                                                                                                                                                  $$S=frac{n(n+1)(n+2)}{3}$$



                                                                                                                                                                  On the other side we have:



                                                                                                                                                                  begin{alignat*}{2}
                                                                                                                                                                  &sum_{k=1}^n k(k+1)&&=sum_{k=1}^n k^2+k \
                                                                                                                                                                  & &&=sum_{k=1}^n k^2+sum_{k=1}^n k \
                                                                                                                                                                  &frac{n(n+1)(n+2)}{3}&&=sum_{k=1}^n k^2+frac{n(n+1)}{2} \
                                                                                                                                                                  &sum_{k=1}^n k^2&&=frac{n(n+1)(n+2)}{3}-frac{n(n+1)}{2} \
                                                                                                                                                                  &sum_{k=1}^n k^2&&=frac{n(n+1)(2n+1)}{6}
                                                                                                                                                                  end{alignat*}







                                                                                                                                                                  share|cite|improve this answer














                                                                                                                                                                  share|cite|improve this answer



                                                                                                                                                                  share|cite|improve this answer








                                                                                                                                                                  edited May 11 '17 at 7:38









                                                                                                                                                                  agc

                                                                                                                                                                  1154




                                                                                                                                                                  1154










                                                                                                                                                                  answered Feb 12 '17 at 18:39









                                                                                                                                                                  OAMAZFOAMAZF

                                                                                                                                                                  1




                                                                                                                                                                  1























                                                                                                                                                                      0












                                                                                                                                                                      $begingroup$

                                                                                                                                                                      It is a quadraic sequence as 1,4,9,16,25,36 ........//



                                                                                                                                                                      Its first term (a)=1
                                                                                                                                                                      1st difference (d)=4-1=3
                                                                                                                                                                      2nd difference i.e. constant difference(c)=2



                                                                                                                                                                      There is a sum formula for any quadraic equation which is



                                                                                                                                                                      Sn=n/6*[(n-1)3d+(n-1)(n-2)c]+an



                                                                                                                                                                      Putting above value in this formula,we get



                                                                                                                                                                      Sn=n/6*[(n-1)3*3+(n^2-3n+2)2]+1n



                                                                                                                                                                       =n/6[9n-9+2n^2-6n+4]+n

                                                                                                                                                                      =n/6[2n^2+3n-5]+n

                                                                                                                                                                      =n/6[2n^2+3n-5+6]

                                                                                                                                                                      =n/6[2n^2+3n+1]

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


                                                                                                                                                                      Which is final answer.There is also sum formula for cubic and even quartic sequence.






                                                                                                                                                                      share|cite|improve this answer











                                                                                                                                                                      $endgroup$









                                                                                                                                                                      • 1




                                                                                                                                                                        $begingroup$
                                                                                                                                                                        Why is the sum formula true then?
                                                                                                                                                                        $endgroup$
                                                                                                                                                                        – Alex Vong
                                                                                                                                                                        May 19 '18 at 17:00










                                                                                                                                                                      • $begingroup$
                                                                                                                                                                        @AlexVong This formula is made by myself using a long theory of sequence.Combining arithmetic sequence formula it is formed
                                                                                                                                                                        $endgroup$
                                                                                                                                                                        – Santosh kurmi
                                                                                                                                                                        May 19 '18 at 17:22












                                                                                                                                                                      • $begingroup$
                                                                                                                                                                        It is real sum formula of quadraic sequence
                                                                                                                                                                        $endgroup$
                                                                                                                                                                        – Santosh kurmi
                                                                                                                                                                        May 19 '18 at 17:26










                                                                                                                                                                      • $begingroup$
                                                                                                                                                                        @AlexVong It is made using Sum formula of AP
                                                                                                                                                                        $endgroup$
                                                                                                                                                                        – Santosh kurmi
                                                                                                                                                                        May 19 '18 at 17:27










                                                                                                                                                                      • $begingroup$
                                                                                                                                                                        Since the question asked why the formula is true, you may want to add the reason to the answer.
                                                                                                                                                                        $endgroup$
                                                                                                                                                                        – Alex Vong
                                                                                                                                                                        May 20 '18 at 5:58
















                                                                                                                                                                      0












                                                                                                                                                                      $begingroup$

                                                                                                                                                                      It is a quadraic sequence as 1,4,9,16,25,36 ........//



                                                                                                                                                                      Its first term (a)=1
                                                                                                                                                                      1st difference (d)=4-1=3
                                                                                                                                                                      2nd difference i.e. constant difference(c)=2



                                                                                                                                                                      There is a sum formula for any quadraic equation which is



                                                                                                                                                                      Sn=n/6*[(n-1)3d+(n-1)(n-2)c]+an



                                                                                                                                                                      Putting above value in this formula,we get



                                                                                                                                                                      Sn=n/6*[(n-1)3*3+(n^2-3n+2)2]+1n



                                                                                                                                                                       =n/6[9n-9+2n^2-6n+4]+n

                                                                                                                                                                      =n/6[2n^2+3n-5]+n

                                                                                                                                                                      =n/6[2n^2+3n-5+6]

                                                                                                                                                                      =n/6[2n^2+3n+1]

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


                                                                                                                                                                      Which is final answer.There is also sum formula for cubic and even quartic sequence.






                                                                                                                                                                      share|cite|improve this answer











                                                                                                                                                                      $endgroup$









                                                                                                                                                                      • 1




                                                                                                                                                                        $begingroup$
                                                                                                                                                                        Why is the sum formula true then?
                                                                                                                                                                        $endgroup$
                                                                                                                                                                        – Alex Vong
                                                                                                                                                                        May 19 '18 at 17:00










                                                                                                                                                                      • $begingroup$
                                                                                                                                                                        @AlexVong This formula is made by myself using a long theory of sequence.Combining arithmetic sequence formula it is formed
                                                                                                                                                                        $endgroup$
                                                                                                                                                                        – Santosh kurmi
                                                                                                                                                                        May 19 '18 at 17:22












                                                                                                                                                                      • $begingroup$
                                                                                                                                                                        It is real sum formula of quadraic sequence
                                                                                                                                                                        $endgroup$
                                                                                                                                                                        – Santosh kurmi
                                                                                                                                                                        May 19 '18 at 17:26










                                                                                                                                                                      • $begingroup$
                                                                                                                                                                        @AlexVong It is made using Sum formula of AP
                                                                                                                                                                        $endgroup$
                                                                                                                                                                        – Santosh kurmi
                                                                                                                                                                        May 19 '18 at 17:27










                                                                                                                                                                      • $begingroup$
                                                                                                                                                                        Since the question asked why the formula is true, you may want to add the reason to the answer.
                                                                                                                                                                        $endgroup$
                                                                                                                                                                        – Alex Vong
                                                                                                                                                                        May 20 '18 at 5:58














                                                                                                                                                                      0












                                                                                                                                                                      0








                                                                                                                                                                      0





                                                                                                                                                                      $begingroup$

                                                                                                                                                                      It is a quadraic sequence as 1,4,9,16,25,36 ........//



                                                                                                                                                                      Its first term (a)=1
                                                                                                                                                                      1st difference (d)=4-1=3
                                                                                                                                                                      2nd difference i.e. constant difference(c)=2



                                                                                                                                                                      There is a sum formula for any quadraic equation which is



                                                                                                                                                                      Sn=n/6*[(n-1)3d+(n-1)(n-2)c]+an



                                                                                                                                                                      Putting above value in this formula,we get



                                                                                                                                                                      Sn=n/6*[(n-1)3*3+(n^2-3n+2)2]+1n



                                                                                                                                                                       =n/6[9n-9+2n^2-6n+4]+n

                                                                                                                                                                      =n/6[2n^2+3n-5]+n

                                                                                                                                                                      =n/6[2n^2+3n-5+6]

                                                                                                                                                                      =n/6[2n^2+3n+1]

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


                                                                                                                                                                      Which is final answer.There is also sum formula for cubic and even quartic sequence.






                                                                                                                                                                      share|cite|improve this answer











                                                                                                                                                                      $endgroup$



                                                                                                                                                                      It is a quadraic sequence as 1,4,9,16,25,36 ........//



                                                                                                                                                                      Its first term (a)=1
                                                                                                                                                                      1st difference (d)=4-1=3
                                                                                                                                                                      2nd difference i.e. constant difference(c)=2



                                                                                                                                                                      There is a sum formula for any quadraic equation which is



                                                                                                                                                                      Sn=n/6*[(n-1)3d+(n-1)(n-2)c]+an



                                                                                                                                                                      Putting above value in this formula,we get



                                                                                                                                                                      Sn=n/6*[(n-1)3*3+(n^2-3n+2)2]+1n



                                                                                                                                                                       =n/6[9n-9+2n^2-6n+4]+n

                                                                                                                                                                      =n/6[2n^2+3n-5]+n

                                                                                                                                                                      =n/6[2n^2+3n-5+6]

                                                                                                                                                                      =n/6[2n^2+3n+1]

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


                                                                                                                                                                      Which is final answer.There is also sum formula for cubic and even quartic sequence.







                                                                                                                                                                      share|cite|improve this answer














                                                                                                                                                                      share|cite|improve this answer



                                                                                                                                                                      share|cite|improve this answer








                                                                                                                                                                      edited May 19 '18 at 17:19

























                                                                                                                                                                      answered May 19 '18 at 16:35









                                                                                                                                                                      Santosh kurmiSantosh kurmi

                                                                                                                                                                      11




                                                                                                                                                                      11








                                                                                                                                                                      • 1




                                                                                                                                                                        $begingroup$
                                                                                                                                                                        Why is the sum formula true then?
                                                                                                                                                                        $endgroup$
                                                                                                                                                                        – Alex Vong
                                                                                                                                                                        May 19 '18 at 17:00










                                                                                                                                                                      • $begingroup$
                                                                                                                                                                        @AlexVong This formula is made by myself using a long theory of sequence.Combining arithmetic sequence formula it is formed
                                                                                                                                                                        $endgroup$
                                                                                                                                                                        – Santosh kurmi
                                                                                                                                                                        May 19 '18 at 17:22












                                                                                                                                                                      • $begingroup$
                                                                                                                                                                        It is real sum formula of quadraic sequence
                                                                                                                                                                        $endgroup$
                                                                                                                                                                        – Santosh kurmi
                                                                                                                                                                        May 19 '18 at 17:26










                                                                                                                                                                      • $begingroup$
                                                                                                                                                                        @AlexVong It is made using Sum formula of AP
                                                                                                                                                                        $endgroup$
                                                                                                                                                                        – Santosh kurmi
                                                                                                                                                                        May 19 '18 at 17:27










                                                                                                                                                                      • $begingroup$
                                                                                                                                                                        Since the question asked why the formula is true, you may want to add the reason to the answer.
                                                                                                                                                                        $endgroup$
                                                                                                                                                                        – Alex Vong
                                                                                                                                                                        May 20 '18 at 5:58














                                                                                                                                                                      • 1




                                                                                                                                                                        $begingroup$
                                                                                                                                                                        Why is the sum formula true then?
                                                                                                                                                                        $endgroup$
                                                                                                                                                                        – Alex Vong
                                                                                                                                                                        May 19 '18 at 17:00










                                                                                                                                                                      • $begingroup$
                                                                                                                                                                        @AlexVong This formula is made by myself using a long theory of sequence.Combining arithmetic sequence formula it is formed
                                                                                                                                                                        $endgroup$
                                                                                                                                                                        – Santosh kurmi
                                                                                                                                                                        May 19 '18 at 17:22












                                                                                                                                                                      • $begingroup$
                                                                                                                                                                        It is real sum formula of quadraic sequence
                                                                                                                                                                        $endgroup$
                                                                                                                                                                        – Santosh kurmi
                                                                                                                                                                        May 19 '18 at 17:26










                                                                                                                                                                      • $begingroup$
                                                                                                                                                                        @AlexVong It is made using Sum formula of AP
                                                                                                                                                                        $endgroup$
                                                                                                                                                                        – Santosh kurmi
                                                                                                                                                                        May 19 '18 at 17:27










                                                                                                                                                                      • $begingroup$
                                                                                                                                                                        Since the question asked why the formula is true, you may want to add the reason to the answer.
                                                                                                                                                                        $endgroup$
                                                                                                                                                                        – Alex Vong
                                                                                                                                                                        May 20 '18 at 5:58








                                                                                                                                                                      1




                                                                                                                                                                      1




                                                                                                                                                                      $begingroup$
                                                                                                                                                                      Why is the sum formula true then?
                                                                                                                                                                      $endgroup$
                                                                                                                                                                      – Alex Vong
                                                                                                                                                                      May 19 '18 at 17:00




                                                                                                                                                                      $begingroup$
                                                                                                                                                                      Why is the sum formula true then?
                                                                                                                                                                      $endgroup$
                                                                                                                                                                      – Alex Vong
                                                                                                                                                                      May 19 '18 at 17:00












                                                                                                                                                                      $begingroup$
                                                                                                                                                                      @AlexVong This formula is made by myself using a long theory of sequence.Combining arithmetic sequence formula it is formed
                                                                                                                                                                      $endgroup$
                                                                                                                                                                      – Santosh kurmi
                                                                                                                                                                      May 19 '18 at 17:22






                                                                                                                                                                      $begingroup$
                                                                                                                                                                      @AlexVong This formula is made by myself using a long theory of sequence.Combining arithmetic sequence formula it is formed
                                                                                                                                                                      $endgroup$
                                                                                                                                                                      – Santosh kurmi
                                                                                                                                                                      May 19 '18 at 17:22














                                                                                                                                                                      $begingroup$
                                                                                                                                                                      It is real sum formula of quadraic sequence
                                                                                                                                                                      $endgroup$
                                                                                                                                                                      – Santosh kurmi
                                                                                                                                                                      May 19 '18 at 17:26




                                                                                                                                                                      $begingroup$
                                                                                                                                                                      It is real sum formula of quadraic sequence
                                                                                                                                                                      $endgroup$
                                                                                                                                                                      – Santosh kurmi
                                                                                                                                                                      May 19 '18 at 17:26












                                                                                                                                                                      $begingroup$
                                                                                                                                                                      @AlexVong It is made using Sum formula of AP
                                                                                                                                                                      $endgroup$
                                                                                                                                                                      – Santosh kurmi
                                                                                                                                                                      May 19 '18 at 17:27




                                                                                                                                                                      $begingroup$
                                                                                                                                                                      @AlexVong It is made using Sum formula of AP
                                                                                                                                                                      $endgroup$
                                                                                                                                                                      – Santosh kurmi
                                                                                                                                                                      May 19 '18 at 17:27












                                                                                                                                                                      $begingroup$
                                                                                                                                                                      Since the question asked why the formula is true, you may want to add the reason to the answer.
                                                                                                                                                                      $endgroup$
                                                                                                                                                                      – Alex Vong
                                                                                                                                                                      May 20 '18 at 5:58




                                                                                                                                                                      $begingroup$
                                                                                                                                                                      Since the question asked why the formula is true, you may want to add the reason to the answer.
                                                                                                                                                                      $endgroup$
                                                                                                                                                                      – Alex Vong
                                                                                                                                                                      May 20 '18 at 5:58











                                                                                                                                                                      -1












                                                                                                                                                                      $begingroup$

                                                                                                                                                                      Another method by using telescoping sum :-
                                                                                                                                                                      We know $(a+b)^3-a^3-b^3=3ab(a+b)$ , take



                                                                                                                                                                      $a=k-1 , b=2$ , then $a+b=k+1$ and $(k+1)^3-(k-1)^3-2^3=6(k-1)(k+1)=6k^2-6$ ,



                                                                                                                                                                      hence $(k+1)^3-(k-1)^3-8+6=(k+1)^3-k^3+k^3-(k-1)^3-2=6k^2$ , taking sum over $k$



                                                                                                                                                                      from $1$ to $n$ we get , $sum_{k=1}^n [(k+1)^3-k^3] + sum_{k=1}^n [k^3-(k-1)^3] -sum_{k=1}^n 2 = 6 sum_{k=1}^nk^2$ , the first



                                                                                                                                                                      sum on the left hand side is telescoping resulting in $(n+1)^3-1$ , the second sum is also telescoping resulting in $n^3-(1-1)^3=n^3$ , and the third sum is simply $2n$ , hence



                                                                                                                                                                      $6 sum_{k=1}^nk^2=(n+1)^3-1+n^3-2n=2n^3+3n^2+n=n(n+1)(2n+1)$






                                                                                                                                                                      share|cite|improve this answer









                                                                                                                                                                      $endgroup$


















                                                                                                                                                                        -1












                                                                                                                                                                        $begingroup$

                                                                                                                                                                        Another method by using telescoping sum :-
                                                                                                                                                                        We know $(a+b)^3-a^3-b^3=3ab(a+b)$ , take



                                                                                                                                                                        $a=k-1 , b=2$ , then $a+b=k+1$ and $(k+1)^3-(k-1)^3-2^3=6(k-1)(k+1)=6k^2-6$ ,



                                                                                                                                                                        hence $(k+1)^3-(k-1)^3-8+6=(k+1)^3-k^3+k^3-(k-1)^3-2=6k^2$ , taking sum over $k$



                                                                                                                                                                        from $1$ to $n$ we get , $sum_{k=1}^n [(k+1)^3-k^3] + sum_{k=1}^n [k^3-(k-1)^3] -sum_{k=1}^n 2 = 6 sum_{k=1}^nk^2$ , the first



                                                                                                                                                                        sum on the left hand side is telescoping resulting in $(n+1)^3-1$ , the second sum is also telescoping resulting in $n^3-(1-1)^3=n^3$ , and the third sum is simply $2n$ , hence



                                                                                                                                                                        $6 sum_{k=1}^nk^2=(n+1)^3-1+n^3-2n=2n^3+3n^2+n=n(n+1)(2n+1)$






                                                                                                                                                                        share|cite|improve this answer









                                                                                                                                                                        $endgroup$
















                                                                                                                                                                          -1












                                                                                                                                                                          -1








                                                                                                                                                                          -1





                                                                                                                                                                          $begingroup$

                                                                                                                                                                          Another method by using telescoping sum :-
                                                                                                                                                                          We know $(a+b)^3-a^3-b^3=3ab(a+b)$ , take



                                                                                                                                                                          $a=k-1 , b=2$ , then $a+b=k+1$ and $(k+1)^3-(k-1)^3-2^3=6(k-1)(k+1)=6k^2-6$ ,



                                                                                                                                                                          hence $(k+1)^3-(k-1)^3-8+6=(k+1)^3-k^3+k^3-(k-1)^3-2=6k^2$ , taking sum over $k$



                                                                                                                                                                          from $1$ to $n$ we get , $sum_{k=1}^n [(k+1)^3-k^3] + sum_{k=1}^n [k^3-(k-1)^3] -sum_{k=1}^n 2 = 6 sum_{k=1}^nk^2$ , the first



                                                                                                                                                                          sum on the left hand side is telescoping resulting in $(n+1)^3-1$ , the second sum is also telescoping resulting in $n^3-(1-1)^3=n^3$ , and the third sum is simply $2n$ , hence



                                                                                                                                                                          $6 sum_{k=1}^nk^2=(n+1)^3-1+n^3-2n=2n^3+3n^2+n=n(n+1)(2n+1)$






                                                                                                                                                                          share|cite|improve this answer









                                                                                                                                                                          $endgroup$



                                                                                                                                                                          Another method by using telescoping sum :-
                                                                                                                                                                          We know $(a+b)^3-a^3-b^3=3ab(a+b)$ , take



                                                                                                                                                                          $a=k-1 , b=2$ , then $a+b=k+1$ and $(k+1)^3-(k-1)^3-2^3=6(k-1)(k+1)=6k^2-6$ ,



                                                                                                                                                                          hence $(k+1)^3-(k-1)^3-8+6=(k+1)^3-k^3+k^3-(k-1)^3-2=6k^2$ , taking sum over $k$



                                                                                                                                                                          from $1$ to $n$ we get , $sum_{k=1}^n [(k+1)^3-k^3] + sum_{k=1}^n [k^3-(k-1)^3] -sum_{k=1}^n 2 = 6 sum_{k=1}^nk^2$ , the first



                                                                                                                                                                          sum on the left hand side is telescoping resulting in $(n+1)^3-1$ , the second sum is also telescoping resulting in $n^3-(1-1)^3=n^3$ , and the third sum is simply $2n$ , hence



                                                                                                                                                                          $6 sum_{k=1}^nk^2=(n+1)^3-1+n^3-2n=2n^3+3n^2+n=n(n+1)(2n+1)$







                                                                                                                                                                          share|cite|improve this answer












                                                                                                                                                                          share|cite|improve this answer



                                                                                                                                                                          share|cite|improve this answer










                                                                                                                                                                          answered Oct 17 '13 at 13:24









                                                                                                                                                                          Souvik DeySouvik Dey

                                                                                                                                                                          4,07711458




                                                                                                                                                                          4,07711458























                                                                                                                                                                              -1












                                                                                                                                                                              $begingroup$

                                                                                                                                                                              If you know that the nth square is the sum of the first n odd numbers, you can rewrite each square in the above sum in that way and do a little bit of rearranging to get the desired identity. In general, knowing the value of (n + 1)^k - n^k allows you to write (n+1)^k as a telescoping sum of a polynomial of degree k-1, running over the values 1 through n. If you know the values of the sums of consecutive powers up to k-1, this allows you to find the sum of consecutive kth powers by substituting the polynomial sum for each kth power.






                                                                                                                                                                              share|cite|improve this answer











                                                                                                                                                                              $endgroup$


















                                                                                                                                                                                -1












                                                                                                                                                                                $begingroup$

                                                                                                                                                                                If you know that the nth square is the sum of the first n odd numbers, you can rewrite each square in the above sum in that way and do a little bit of rearranging to get the desired identity. In general, knowing the value of (n + 1)^k - n^k allows you to write (n+1)^k as a telescoping sum of a polynomial of degree k-1, running over the values 1 through n. If you know the values of the sums of consecutive powers up to k-1, this allows you to find the sum of consecutive kth powers by substituting the polynomial sum for each kth power.






                                                                                                                                                                                share|cite|improve this answer











                                                                                                                                                                                $endgroup$
















                                                                                                                                                                                  -1












                                                                                                                                                                                  -1








                                                                                                                                                                                  -1





                                                                                                                                                                                  $begingroup$

                                                                                                                                                                                  If you know that the nth square is the sum of the first n odd numbers, you can rewrite each square in the above sum in that way and do a little bit of rearranging to get the desired identity. In general, knowing the value of (n + 1)^k - n^k allows you to write (n+1)^k as a telescoping sum of a polynomial of degree k-1, running over the values 1 through n. If you know the values of the sums of consecutive powers up to k-1, this allows you to find the sum of consecutive kth powers by substituting the polynomial sum for each kth power.






                                                                                                                                                                                  share|cite|improve this answer











                                                                                                                                                                                  $endgroup$



                                                                                                                                                                                  If you know that the nth square is the sum of the first n odd numbers, you can rewrite each square in the above sum in that way and do a little bit of rearranging to get the desired identity. In general, knowing the value of (n + 1)^k - n^k allows you to write (n+1)^k as a telescoping sum of a polynomial of degree k-1, running over the values 1 through n. If you know the values of the sums of consecutive powers up to k-1, this allows you to find the sum of consecutive kth powers by substituting the polynomial sum for each kth power.







                                                                                                                                                                                  share|cite|improve this answer














                                                                                                                                                                                  share|cite|improve this answer



                                                                                                                                                                                  share|cite|improve this answer








                                                                                                                                                                                  edited Mar 3 '16 at 17:18

























                                                                                                                                                                                  answered Mar 3 '16 at 17:10









                                                                                                                                                                                  Vik78Vik78

                                                                                                                                                                                  2,154616




                                                                                                                                                                                  2,154616

















                                                                                                                                                                                      protected by Jyrki Lahtonen May 19 '18 at 17:31



                                                                                                                                                                                      Thank you for your interest in this question.
                                                                                                                                                                                      Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).



                                                                                                                                                                                      Would you like to answer one of these unanswered questions instead?



                                                                                                                                                                                      Popular posts from this blog

                                                                                                                                                                                      Berounka

                                                                                                                                                                                      Sphinx de Gizeh

                                                                                                                                                                                      Different font size/position of beamer's navigation symbols template's content depending on regular/plain...