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

**ling_c_0202** · October 30th 2006, 06:58 AM

Can anyone tell me how to get a formula for

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

**ThePerfectHacker** · October 30th 2006, 07:44 AM

Originally Posted by ling_c_0202

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}$

**Soroban** · October 30th 2006, 10:18 AM

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}\!\!\! \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}$

**ling_c_0202** · November 1st 2006, 08:10 AM

o.... i 've got it!
Thank you very much!
The approach is really wonderful ^^

**Soroban** · November 1st 2006, 10:17 AM

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} \begin{array}{ccccccc}-\\-\\-\\ \vdots \\ - \\ - \\ -\end{array} \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} \begin{array}{ccccccc}-\\-\\-\\ \vdots \\-\\-\\-\end{array} \begin{array}{ccccccc}3n \\3(n\!-\!1)\\3(n\!-\!2)\\ \vdots \\ 3\cdot3\\3\cdot2\\3\cdot1\end{array} \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}}$

**srinivas** · November 15th 2006, 10:14 AM

what about summation from 0 to n x^x
does it have a formula??

**ThePerfectHacker** · November 15th 2006, 12:48 PM

Originally Posted by srinivas

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).

**Jameson** · November 15th 2006, 07:38 PM

Wow Soroban. Just wow.

**TriKri** · November 16th 2006, 06:44 AM

Originally Posted by srinivas

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?

**ThePerfectHacker** · November 16th 2006, 08:44 AM

Originally Posted by TriKri

Aha, I thought you meant $1^1 + 2^2 + 3^3 + ... + n^n$

Any formula for that one?

Not necessarily.

Thread: 1^2 + 2^2 + 3^2 + ... + n^2

LinkBack

Thread Tools

Display

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

thank you