Results 1 to 13 of 13

Math Help - 1^2 + 2^2 + ... + n^2 = ?

  1. #1
    Junior Member
    Joined
    Aug 2008
    From
    Chicago, IL
    Posts
    73

    1^2 + 2^2 + ... + n^2 = ?

    I need a simpler formula for that expression. Im supposed to prove by induction that the number of squares within an n x n checkerboard is that expression. I definately need a simpler formula, but any help towards the proof would be appreciated, thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,415
    Thanks
    1853
    Quote Originally Posted by Dubulus View Post
    I need a simpler formula for that expression. Im supposed to prove by induction that the number of squares within an n x n checkerboard is that expression. I definately need a simpler formula, but any help towards the proof would be appreciated, thanks!
    Generally speaking, if you are adding terms, each of which is a polynomial degree N, then the sum is a polynomial of degree N+1. Here each term is of degree 2 so the sum is a polynomial of degree 3: ax^3+ bx^2+ cx+ d. When n= 1, the sum is 1 so a+ b+ c+ d= 1. When n= 2, the sum is 1+ 4= 5 so 8a+ 4b+ 2c+ d= 5. When n= 3, the sum is 1+ 4+ 9= 14 so 27a+ 9b+ c+ d= 14. Finally, when n= 4, the sum is 1+ 4+ 9+ 16= 30 so 64a+ 16b+ 4c+ d= 30. Solve those 4 equations for a, b, c, d.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Aug 2008
    Posts
    120
    If you just need the formula.

    \sum_{i=1}^n i^2=\frac{n(n+1)(2n+1)}{6}
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Nov 2008
    Posts
    1
    The formula for the sum of squares of first n natural numbers is given by:
    1^2+2^2+3^2+..........+n^2 = n(n+1)(2n+1)/6, ................ eqn(1)

    and as far as the proof is concerned, it can be proved by using the concept of mathematical induction as follows:-
    Let n= 1, therefore L.H.S of the above expression becomes
    1^2 = 1
    and R.H.S becomes
    1(1+1)(2x1+1)/6
    =6/6
    =1
    Hence the result is true for n=1.

    Let us suppose that the result is true for n=k,i.e.
    1^2+2^2+3^2+..........+k^2 = k(k+1)(2k+1)/6

    Let us prove the result for n=k+1.
    If we put n = k+1 on the L.H.S of the eqn (1) then it becomes
    1^2+2^2+3^2+..........+k^2+(k+1)^2
    =k(k+1)(2k+1)/6 + (k+1)^2
    =(k+1){k(2k+1)/6 +(k+1)}
    =(k+1)[{k(2k+1)+6(k+1)}/6]
    =(k+1)[{2(k)^2+k+6k+6}/6]
    =(k+1){2(k)^2+7k+6}/6

    Now let us put n=k+1 on the R.H.S of eqn (1),we have
    (k+1)((k+1)+1)(2(k+1)+1)
    =(k+1)(k+2)(2k+3)
    =(k+1){2(k)^2+7k+6}/6

    Hence L.H.S = R.H.S,
    Hence the result is true for n=k+1 whenever it is true for n=k.
    Thus it is true for all n.

    I hope this will help you in clarifying your doubts.

    For more details on other topics like probability check out my link
    http://mysteriousmathematicssimplified.blogspot.com/
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Aug 2008
    Posts
    120
    There is a beautiful proof not using induction but rather calculus. Try come up with it.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member bkarpuz's Avatar
    Joined
    Sep 2008
    From
    R
    Posts
    481
    Thanks
    2

    Exclamation

    In general, you can easily estimate
    \sum_{i=0}^{n-1}i^{k},
    where n,k\in\mathbb{N}.
    But before let me introduce some basic concepts on difference operator, factorial function and the Stirling numbers.
    The forwards difference operator is defined to be \Delta f(n)=f(n+1)-f(n).
    And the factorial function for n,k\in\mathbb{N} is defined as n^{(k)}:=n(n-1)\cdots(n-k+1) (exactly n numbers of successive terms are being factored), and for convenience n^{(0)}:=1.
    It is not hard to see that
    \Delta n^{(k)}=kn^{(k-1)} and \sum_{i=0}^{n-1}i^{(k-1)}=\sum_{i=0}^{n-1}\frac{1}{k}\Delta i^{(k)}=\frac{n^{(k)}}{k}
    are true.
    Now, let s and S satisfy the following relations:
    n^{(k)}=\sum_{j=1}^{k}s(k,j)n^{j}
    and
    n^{k}=\sum_{j=0}^{k}S(k,j)n^{(j)},
    which are called as the Stirling numbers of first and second kind, respectively (also see Stirling number - Wikipedia, the free encyclopedia).
    Then, lets turn back to the problem.
    \sum_{i=0}^{n-1}i^{k}=\sum_{i=0}^{n-1}\sum_{j=0}^{k}S(k,j)i^{(j)}
    ......... =\sum_{j=0}^{k}S(k,j)\sum_{i=0}^{n-1}i^{(j)}
    ......... =\sum_{j=0}^{k}S(k,j)\frac{1}{j+1}\sum_{i=0}^{n-1}\Delta i^{(j+1)}
    ......... =\sum_{j=0}^{k}S(k,j)\frac{1}{j+1}n^{(j+1)}
    ......... =\sum_{j=0}^{k}S(k,j)\frac{1}{j+1}\sum_{\ell=1}^{j  +1}s(j+1,\ell)n^{\ell}
    ......... =\sum_{j=0}^{k}\sum_{\ell=0}^{j}\frac{S(k,j)s(j+1,  \ell+1)}{j+1}n^{\ell+1}.
    Finally, if k is known, you may simplify the last term above.
    Check the result for k=2.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member DeMath's Avatar
    Joined
    Nov 2008
    From
    Moscow
    Posts
    473
    Thanks
    5
    We can use more simple formula to find a sum 1^m+2^m+...+n^m:

    \sum\limits_{k = 1}^n {k^m }  = \frac{{(n + 1)^{m + 1}  - 1}}{{m + 1}} - \frac{1}{{m + 1}}\sum\limits_{s = 1}^m {\left[ {\frac{{\left( {m + 1} \right)!}}{{\left( {m - s} \right)!\left( {s + 1} \right)!}}\sum\limits_{k = 1}^n {k^{m - s} } } \right]} ,{\text{ }}m \in \mathbb{Z}^ +  .

    We can deduce this formula with a binomial theorem.
    Last edited by DeMath; January 5th 2009 at 02:51 PM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Dec 2008
    From
    Wellington ,FL
    Posts
    19

    Wink

    Quote Originally Posted by DeMath View Post
    We can use more simple formula to find a sum 1^m+2^m+...+n^m:

    \sum\limits_{k = 1}^n {k^m } = \frac{{(n + 1)^{m + 1} - 1}}{{m + 1}} - \frac{1}{{m + 1}}\sum\limits_{s = 1}^m {\left[ {\frac{{\left( {m + 1} \right)!}}{{\left( {m - s} \right)!\left( {s + 1} \right)!}}\sum\limits_{k = 1}^n {k^{m - s} } } \right]} ,{\text{ }}m \in \mathbb{Z}^ + .

    We can deduce this formula with a binomial theorem.
    I agree with my countryman.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by DeMath View Post
    We can use more simple formula to find a sum 1^m+2^m+...+n^m:

    \sum\limits_{k = 1}^n {k^m }  = \frac{{(n + 1)^{m + 1}  - 1}}{{m + 1}} - \frac{1}{{m + 1}}\sum\limits_{s = 1}^m {\left[ {\frac{{\left( {m + 1} \right)!}}{{\left( {m - s} \right)!\left( {s + 1} \right)!}}\sum\limits_{k = 1}^n {k^{m - s} } } \right]} ,{\text{ }}m \in \mathbb{Z}^ +  .

    We can deduce this formula with a binomial theorem.
    I am worried about the "simplicity" of this formula...

    Doesnt \sum\limits_{s = 1}^m {\left[ {\frac{{\left( {m + 1} \right)!}}{{\left( {m - s} \right)!\left( {s + 1} \right)!}}\sum\limits_{k = 1}^n {k^{m - s} } } \right]} look more formidable than 1^m+2^m+...+n^m?

    Or do you have a closed form solution for that beast?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Jan 2009
    Posts
    2
    I do not think there is a closed formula...but i may be wrong
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor Mathstud28's Avatar
    Joined
    Mar 2008
    From
    Pennsylvania
    Posts
    3,641
    Quote Originally Posted by Isomorphism View Post
    I am worried about the "simplicity" of this formula...

    Doesnt \sum\limits_{s = 1}^m {\left[ {\frac{{\left( {m + 1} \right)!}}{{\left( {m - s} \right)!\left( {s + 1} \right)!}}\sum\limits_{k = 1}^n {k^{m - s} } } \right]} look more formidable than 1^m+2^m+...+n^m?

    Or do you have a closed form solution for that beast?
    To add on to this...would you have to calculate \sum_{k=1}^{n}k^{2},\sum_{k=1}^{n}k^3,\cdots,\sum_  {k=1}^{n}k^{m-1} haha
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Senior Member DeMath's Avatar
    Joined
    Nov 2008
    From
    Moscow
    Posts
    473
    Thanks
    5
    Quote Originally Posted by Isomorphism View Post
    I am worried about the "simplicity" of this formula...

    Doesnt \sum\limits_{s = 1}^m {\left[ {\frac{{\left( {m + 1} \right)!}}{{\left( {m - s} \right)!\left( {s + 1} \right)!}}\sum\limits_{k = 1}^n {k^{m - s} } } \right]} look more formidable than 1^m+2^m+...+n^m?

    Or do you have a closed form solution for that beast?
    Of course, you're right.
    I wanted to show that we can represent 1^m+2^m+...+n^m as the amount of the amounts of less powers m with the binomial theorem.

    I am sorry, I perhaps incorrectly said that the formula is simple.
    Last edited by DeMath; January 9th 2009 at 06:25 PM.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Flow Master
    mr fantastic's Avatar
    Joined
    Dec 2007
    From
    Zeitgeist
    Posts
    16,948
    Thanks
    5
    Judging from the number of off-topic posts this thread collected at its tail-end (and which you can now find here: http://www.mathhelpforum.com/math-he...countries.html), I'd say that nothing much more that's on-topic is going to get added so (drum roll, maestro, if you please) .......

    Thread closed.
    Follow Math Help Forum on Facebook and Google+


/mathhelpforum @mathhelpforum