Results 1 to 10 of 10

Math Help - 1^2 + 2^2 + 3^2 + ... + n^2

  1. #1
    Junior Member
    Joined
    Dec 2005
    Posts
    40

    1^2 + 2^2 + 3^2 + ... + n^2

    Can anyone tell me how to get a formula for

    1^2 + 2^2 + 3^2 + ... + n^2, where n is a positive integer.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by ling_c_0202 View Post
    Can anyone tell me how to get a formula for

    1^2 + 2^2 + 3^2 + ... + n^2, where n is a positive integer.
    The formula is,
    \frac{n(n+1)(2n+1)}{6}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,711
    Thanks
    632
    Hello, ling_c_0202!

    I'll show you a primitive method for this problem.


    Can anyone tell me how to get a formula for:

    . . 1^2 + 2^2 + 3^2 + \cdots + n^2, where n is a positive integer.

    Crank out the first few sums and take consecutive differences.
    Then take differences of the differences, etc., until we get a constant sequence.

    \begin{array}{cccccc}S_1 & = \\ S_2 & = \\ S_3 & = \\ S_4 & = \\ S_5 & = \\ S_6 & =\end{array}\begin{array}{cccccc}1^2\\ 1^2+2^2\\1^2+2^3+3^2\\1^2+2^2+3^2+4^2 \\1^2+2^2+3^2+4^2+5^2 \\ 1^2+2^2+3^2+4^2+5^2+6^2\end{array}\begin{array}{cc  cccc}= \\ = \\ = \\ = \\ = \\ =\end{array}\begin{array}{cccccc}1 \\ 5 \\ 14 \\ 30 \\ 55 \\ 91\end{array}\!\!\!<br />
\begin{array}{ccccc}\} \\ \} \\ \}\\ \} \\ \}\end{array}\!\!\!\begin{array}{ccccc}4 \\ 9\\ 16 \\25\\36\end{array}\!\!\!\begin{array}{cccc}\} \\ \} \\ \} \\ \}\end{array}\!\!\!\begin{array}{cccc}5 \\ 7 \\ 9 \\ 11\end{array} \begin{array}{ccc}\} \\ \} \\ \}\end{array}\!\!\!\begin{array}{ccc}2\\2\\2\end{a  rray}

    We get a constant sequence at the third differences.
    This tells us that the generating function of of the third degree (a cubic).

    We have the general cubic function: . f(n) \:=\:an^3 + bn^2 + cn + d
    . . and we must determine a,\,b,\,c,\,d.


    We will use the first four sums from our list.

    \begin{array}{cccc}n=1: \\n=2: \\ n=3: \\ n=4:\end{array}\begin{array}{cccc}a\cdot1^3 + b\cdot1^2+c\cdot1 + d \:=\\ a\cdot2^3 + b\cdot2^2 + c\cdot2 + d\:= \\ a\cdot3^3 + b\cdot3^2 + c\cdot3 + d \:=\\ a\cdot4^3 + b\cdot4^2 + c\cdot4 + d\:=\end{array}\begin{array}{cccc}1\\5\\14\\30\end  {array}\;\begin{array}{cccc}\Rightarrow \\ \Rightarrow \\ \Rightarrow \\ \Rightarrow\end{array} \begin{array}{cccc}a + b + c + d \\ 8a + 4b + 2c + d \\ 27a + 9b + 3c + d \\ 64a + 16b + 4c + d\end{array}\begin{array}{cccc}=\\=\\=\\=\end{arra  y}\begin{array}{cccc}1\\5\\14\\30\end{array} . \begin{array}{cccc}(1)\\(2)\\(3)\\(4)\end{array}


    Now we must solve the system of equations, but it's quite simple . . .

    \begin{array}{ccc}\text{Subtract (1) from (2):} \\ \text{Subtract (2) from (3):} \\ \text{Subtract (3) from (4):}\end{array}\begin{array}{ccc}7a + 3b + c\\19a + 5b + c\\37a + 7b + c\end{array}\begin{array}{ccc}=\\=\\=\end{array}\b  egin{array}{ccc}4\\9\\16\end{array}\;\begin{array}  {ccc}(5)\\(6)\\(7)\end{array}

    \begin{array}{cc}\text{Subtract (5) from (6):} \\ \text{Subtract (6) from (7):}\end{array}\begin{array}{cc}12a + 2b\;=\;5\\18a+2b\;=\;7\end{array}\;\begin{array}{c  c}(8)\\(9)\end{array}

    \text{Subtract (8) from (9): }\;6a\:=\:2\quad\Rightarrow\quad a = \frac{1}{3}

    Back-substitute and get: . b = \frac{1}{2},\;c = \frac{1}{6},\;d = 0


    Hence: . f(n)\;=\;\frac{1}{3}n^3 + \frac{1}{2}n^2 + \frac{1}{6}n

    Therefore: . \sum^n_{k=1}k^2\;=\;\frac{n(n+1)(2n+1)}{6}

    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Dec 2005
    Posts
    40

    thank you

    o.... i 've got it!
    Thank you very much!
    The approach is really wonderful ^^
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,711
    Thanks
    632
    Hello, ling_c_0202 and all!

    Here's another approach to Sums-of-powers formulas.
    (I'll give you the 'long version'.)


    If we know the "previous" sums, say: . \sum^n_{k=1} 1 \:=\:n . and . \sum^n_{k=1}k \:=\:\frac{n(n+1)}{2}
    . .we can find the "next" formula: . \sum^n_{k=1}k^2


    Consider the next-higher power (3) and the difference of two consecutive cubes:
    . . k^3 - (k-1)^3\;=\;3k^2 - 3k + 1


    Now let k \:= \:n,\,n\!-\!1,\,n\!-\!2,\,\hdots,\,3,\,2,\,1 and "stack" the equations.

    \begin{array}{ccccccc}k=n:\\k=n\!-\!1:\\k=n\!-\!2:\\ \vdots \\ k=3:\\k=2:\\ k=1: \end{array} . \begin{array}{ccccccc}n^3 \\ (n\!-\!1)^3 \\ (n\!-\!2)^3 \\ \vdots \\ 3^3 \\ 2^3 \\ 1^3 \end{array}<br />
\begin{array}{ccccccc}-\\-\\-\\ \vdots \\ - \\ - \\ -\end{array}<br />
\begin{array}{ccccccc}(n\!-\!1)^3 \\ (n\!-\!2)^3 \\ (n\!-\!3)^3 \\ \vdots \\ 2^3\\1^3\\0^3\end{array} . \begin{array}{cccccc}=\\=\\=\\ \vdots \\ =\\=\\=\end{array} . \begin{array}{ccccccc}3n^2\\3(n\!-\!1)^2\\3(n\!-\!2)^2\\ \vdots \\ 3\cdot3^2\\3\cdot2^2\\3\cdot1^2\end{array}<br />
\begin{array}{ccccccc}-\\-\\-\\ \vdots \\-\\-\\-\end{array}<br />
\begin{array}{ccccccc}3n \\3(n\!-\!1)\\3(n\!-\!2)\\ \vdots \\ 3\cdot3\\3\cdot2\\3\cdot1\end{array}<br />
\begin{array}{ccccccc} +\;1\\ +\;1 \\ +;1\\ \vdots \\ +\;1 \\ +\;1 \\ +\;1\end{array}
    . . . . . . . . . . . . . . . . . . . . . . . . . . . \downarrow . . . . . . . . \downarrow   . . . . \downarrow
    Add the equations: . . n^3 \qquad\quad\;\;= \quad 3\sum^n_{k=1}k^2 \;\;\;-\;\;\; 3\sum^n_{k=1}k \;+ \;\sum^n_{k=1}1
    . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . \downarrow . . . . \downarrow
    And we have: . . . . . n^3\qquad\quad \;\;=\quad3\sum^n_{k=1} k^2 \;- \;3\!\cdot\!\frac{n(n+1)}{2} \;+ \;n


    Solve for \sum^n_{k=1}k^2: . 3\sum^n_{k=1}k^2\;=\;n^3 - n + \frac{3n(n+1)}{2} \;=\;n(n+1)(n-1) + \frac{3n(n+1)}{2}

    Factor: . 3\sum^n_{k=1}k^2\;=\;\frac{n(n+1)}{2}\left[2(n-1) + 3\right] \;=\;\frac{n(n+1)}{2}(2n + 1)


    Therefore: . \boxed{\sum^n_{k=1}k^2\;=\;\frac{n(n+1)(2n+1)}{6}}

    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Nov 2006
    Posts
    11

    Question

    what about summation from 0 to n x^x
    does it have a formula??
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by srinivas View Post
    what about summation from 0 to n x^x
    does it have a formula??
    I think you are reffering heir. I forgot who solved it from the 17th Century using Bernoulli numbers (I know it was not Bernoulli himself).
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Oct 2005
    From
    Earth
    Posts
    1,599
    Wow Soroban. Just wow.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member TriKri's Avatar
    Joined
    Nov 2006
    Posts
    357
    Thanks
    1
    Quote Originally Posted by srinivas View Post
    what about summation from 0 to n x^x
    does it have a formula??
    Aha, I thought you meant 1^1 + 2^2 + 3^3 + ... + n^n
    Any formula for that one?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by TriKri View Post
    Aha, I thought you meant 1^1 + 2^2 + 3^3 + ... + n^n
    Any formula for that one?
    Not necessarily.
    Follow Math Help Forum on Facebook and Google+


/mathhelpforum @mathhelpforum