Formula for 1+(1+2)+(1+2+3)+(1+2+3+4)+...

Printable View

August 2nd 2006, 07:59 AM
OReilly

Formula for 1+(1+2)+(1+2+3)+(1+2+3+4)+...

Can someone show me the formula for calculating 1+(1+2)+(1+2+3)+(1+2+3+4)+...
August 2nd 2006, 09:03 AM
ThePerfectHacker

Quote:

Originally Posted by OReilly

Can someone show me the formula for calculating 1+(1+2)+(1+2+3)+(1+2+3+4)+...

Yes, I presume you have a finite sum.
---
The key in the the fact that,
$1+2+...+x=\frac{x(x+1)}{2}$
---
Therefore, that entire sum is,
$\frac{1(2)}{2}+\frac{2(3)}{2}+...+\frac{n(n+1)}{2}$
Thus,
$\sum_{k=1}^{n}\frac{k(k+1)}{2}=\frac{1}{2}\sum_{k= 1}^n k^2+k$
Thus, subdivide the summation,
$\frac{1}{2}\sum_{k=1}^n k^2+\frac{1}{2}\sum_{k=1}^n k$
Use the fact above, and the sum of squares formula,

$\frac{1}{2}\cdot \frac{n(n+1)}{2}+\frac{1}{2}\cdot \frac{n(n+1)(2n+1)}{6}$
Simplify,
$\frac{n(n+1)}{4}+\frac{n(n+1)(2n+1)}{12}$
Add, common denominator and add,
$\frac{3n(n+1)+n(n+1)(2n+1)}{12}$
Thus, (factor),
$\frac{n(n+1)(3+2n+1)}{12}$
Simplify again,
$\frac{n(n+1)(2n+4)}{12}$
Simplify again,
$\frac{n(n+1)(n+2)}{6}$
~~~
Just for refernce, the sum of squares formula is,
$\sum_{k=1}^nk^2=\frac{n(n+1)(2n+1)}{6}$
----
I think it is cool that,
$\left( \begin{array}{c}n+2\\3 \end{array} \right)=\frac{(n+2)(n+1)n}{3!}$

That means you can calculate the sum by taking 2 more than number of terms and finding the number of combinations of forming three.
August 2nd 2006, 09:51 AM
OReilly

Thanks!

I didn't know sum of squares formula. :o
August 2nd 2006, 12:26 PM
Soroban

Hello,OReilly!

TPHacker is absolutely correct . . . Nice job, T.P. !

If we are desperate, we could find the formula "from scratch".

Quote:

Can someone show me the formula for calculating:
. . . $1+(1+2)+(1+2+3)+(1+2+3+4)+\hdots$

Crank out a list of the first few sums:

$\begin{array}{ccccccccc}S_1\:=\:1 \\ S_2\:=\:1 + 3\:=\:4\\S_3\:=\:1 + 3 + 6\:=\:10\\ S_4\:=\:1 + 3+6+10 \:=\:20\\ S_5\:=\:1+3+6+10+15\:=\:35 \\S_6\:=\:1+3+6+10+15+21\:=\:56\\ S_7\:=\:1+3+6+10+15+21+28 \;=\;84\\ \vdots\end{array}$

We have a function $f(n)$ . .For $n = 1,2,3,\hdots$

. . the function has consecutive values: . $1\quad4\quad10\quad20\quad56\quad84\;\hdots$

Take differences of consecutive terms: . . $3\quad6\quad\;10\;\quad15\quad21\;\hdots$

Take differences again: . . . . . . . . . . . . . . $3\quad\;4\quad\;\;5\quad\;\;6\;\hdots$

Take differences again: . . . . . . . . . . . . . . . $1\quad\;1\quad\;\:1\;\hdots$

We have a series of constants at the third differences.
. . Hence, $f(n)$ is a third-degree polynomial ... a cubic.

Hence, the function is of the form: . $f(n)\:=\:an^3 + bn^2 + cn + d$
. . and we must determine $a,b,c,d.$

Use the first four values from our list.

$S_1\,=\,1:\;\;a\cdot1^3 + b\cdot1^2 + c\cdot1 + d\:=$ $\:1\quad\;\;\;\Rightarrow\quad\;\; a+b+c+d\;=\;1$
$S_2\,=\,4:\;\;a\cdot2^3 + b\cdot2^2 + c\cdot2 + d \:= \:$ $4\;\;\;\quad\Rightarrow\quad\; 8a + 4b +2c + d \;= \;4$
$S_3\,=\,10:\;a\cdot3^3 + b\cdot3^2 + c\cdot3 + d \:=$ $\:10\quad\Rightarrow\quad 27a + 9b + 3c + d \;= \;10$
$S_4\,=\,20:\;a\cdot4^3 + b\cdot4^2 + c\cdot4 + d\:=$ $\:20\quad\Rightarrow\quad 64a + 16b + 4c + d \;= \;20$

Now we must solve this system of equations . . . but it's easy!

. . $\begin{array}{cccc}a+b+c+d\:=\:1 \\ 8a + 4b + 2c + d \:=\:4 \\ 27a + 9b + 3c + d \:= \:10\\ 64a + 16b + 4c + d \:=\:20\end{array}\;\begin{array}{cccc}(1)\\(2)\\( 3)\\(4)\end{array}$

Subtract (1) from (2): . $7a + 2b + c \:= \:3\quad\;\;\;(5)$
Subtract (2) from (3): . $19a + 5b + c \:= \:6\quad\;(6)$
Subtract (3) from (4): . $376a + 7b + c \:= \:10\;\;(7)$

Subtract (5) from (6): . $12a + 2b\:=\:3\;\;(8)$
Subtract (6) from (7): . $18a + 2b\:=\:4\;\;(9)$

Subtract (8) from (9): . $6a\,=\,1\quad\Rightarrow\quad \boxed{a = \frac{1}{6}}$

Substitute into (8): . $12\left(\frac{1}{6}\right) + 2b\:=\:3\quad\Rightarrow\quad \boxed{b = \frac{1}{2}}$

Substitute into (5): . $7\left(\frac{1}{6}\right) + 3\left(\frac{1}{2}\right) + c\:=\:3\quad\Rightarrow\quad \boxed{c = \frac{1}{3}}$

Substitute into (1): . $\frac{1}{6} + \frac{1}{2} + \frac{1}{3} + d\:=\:1\quad\Rightarrow\quad \boxed{d = 0}$

Therefore: . $f(n)\:=\:\frac{1}{6}n^3 + \frac{1}{2}n^2 + \frac{1}{3}n\quad\Rightarrow\quad \boxed{f(n)\;=\;\frac{n(n+1)(n+2)}{6}}$

~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

This "scratch"method can be used
. . when we suspect we have a polynomial function.
It is long and tedious, but it works.

Of course, it is more efficient to learn a few sums-of-powers formula:

. . $\sum_{k=1}^n k \;= \;\frac{n(n+1)}{2}$

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

. . $\sum_{k=1}^n k^3\;= \;\frac{n^2(n+1)^2}{4}$

Note that the third formula is the square of the first formula,
. . making it easier to memorize.

But what about the implications?
. . This means: . $(1 + 2 + 3 + 4 + 5)^2\:=\:1^3+2^3+3^3+4^3+5^3$

It looks like a bad joke or a terrible blunder, doesn't it?
August 2nd 2006, 01:05 PM
ThePerfectHacker

Quote:

Originally Posted by Soroban

We have a series of constants at the third differences.
. . Hence, $f(n)$ is a third-degree polynomial ... a cubic.

Tell me something, is this a famous method? This is the second time I seen it used on this forum. When I was younger I developed many theorems concerning differences of a sequence. One of them you just used. (A sequence is a polynomial of degree n if and only if it takes n steps to reach a constanct sequence).
---
I have a elegant prove with this rule that,
$a^{(m)}_k=\sum_{k=1}^nk^m$ is always a polynomial sequence.

Consider an infinite sequence,
$0^m,1^m+0^m,2^m+1^m+0^m,...$
Its diffrence sequence is,
$0^m,1^m,2^m,3^m,...$
A polynomial sequence of degree $m$ therefore $m$ subtractions are required. In total we used $m+1$ subtractions on our original sequence. Thus there exists a polynomial sequence of degree $m+1$ . Furthermore, the first coefficient is $\frac{1}{(m+1)!}$ . Based on the fact the constant sequence follows the factorial.
August 2nd 2006, 01:15 PM
CaptainBlack

Quote:

Originally Posted by ThePerfectHacker

Tell me something, is this a famous method?

Yes, I seem to recall that it is associated with Newton's name, but that
be a manifestation of false memory syndrome, but it is in Acton's
"Numerical Methods that Work", which I swear by :)

RonL
August 2nd 2006, 03:25 PM
Soroban

Hello, TPHacker!

Quote:

Tell me something, is this a famous method?

I'm sure it is . . .

I ran across many years ago in some book. .Since then, I've seen more efficient methods,
but I like that very primitive method. .(But I don't use it unless I am forced to.)

In case anyone is interested . . .
I was shown this method in graduate school . . . quite an eye-opener.

To find, for example, $\sum^n_{k=1} k^4$ , we are expected to know the three "preceding" formulas:
. . $\sum^n_{k=1} k \:=\:\frac{n(n+1)}{2}\qquad\sum^n_{k=1} k^2 \:=\:\frac{n(n+1)(2n+1)}{6}\qquad\sum^n_{k=1}$ $k^3\:=\:\frac{n^2(n+1)^2}{4}$

Consider the next-higher power and form: . $k^5 - (k-1)^5$

We have: / $k^5 - (k-1)^5\:=\;5k^4 - 10k^3 + 10k^2 - 5k + 1$

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

. . . . $n^5 - (n-1)^5\;=\quad\;\;5n^4\quad -\quad\;\; 10n^3\quad +$ . . $10n^2\quad\; -\quad\; 5n\quad\; + 1$
$(n-1)^5-(n-2)^5 \;=$ $\:5(n-1)^4 - 10(n-1)^3 + 10(n-1)^2 - 5(n-1) + 1$
$(n-2)^5-(n-3)^5 \;=$ $\:5(n-2)^4 - 10(n-2)^3 + 10(n-2)^2 - 5(n-2) + 1$
. . . . . . $\vdots$ . . . . . . . . . . . $\vdots$ . . . . . . . . $\vdots$ . . . . . . . $\vdots$ . . . . . . . $\vdots$ . . . $\vdots$
. . $3^5\quad -\quad 2^5 \qquad= \quad\;\;5(3^4)\;\;\; -\;\;\; 10(3^3)$ . $+\;\;\; 10(3^2)\quad -\quad 5(3)\quad + 1$
. . $2^5\quad -\quad 1^5\qquad = \quad\;\;5(2^4)\;\;\; -\;\;\; 10(2^3)$ . $+\;\;\; 10(2^2)\quad -\quad 5(2)\quad + 1$
. . $1^5\quad -\quad 0^5 \qquad = \quad\;\;5(1^4)\;\;\; -\;\;\; 10(1^3)$ . $+ \;\;\;10(1^2)\quad -\quad 5(1)\quad + 1$

Add the stack (most of the left side cancels out):

. . $n^5\;=\;5\left(\sum k^4\right) - 10\left(\sum k^3\right) +$ $10\left(\sum k^2\right) - 5\left(\sum k\right) + \left(\sum 1\right)$

We have: . $n^5 \;= \;5\left(\sum k^4\right)-10\cdot\frac{n^2(n+1)^2}{4} +$ $10\cdot\frac{n(n+1)(2n+1)}{6} - 5\cdot\frac{n(n+1)}{2} + n$

Then, after an enormous amount of algebra, we get:

. . . . $\boxed{\sum^n_{k=1} k^4\;=\;\frac{n(n+1)(2n+1)(3n^2 + 3n - 1)}{30}}$

Quick! . . . Add that to your list!
August 2nd 2006, 03:42 PM
Quick

Quote:

Originally Posted by Soroban

Quick! . . . Add that to your list!

for a second I thought you were talking to me. :rolleyes: :D
August 2nd 2006, 04:16 PM
ThePerfectHacker

This problem with the generalized exponent sum, I think, is a very elegant problem. The method I used is solving a system of equations which is the most primitive and complicated method. I then tried to find the patterns for these numbers... and failed. Later I learned the problem was solved in the 18th Century using bernouilli numbers.
---
However, I believe I found an elegant way how to solve that nasty system of equations. I have not yet worked it out but I believe it might work. My idea, is that the matrix that you get is also the solution of the polynomial of best fit which can be calculated with least squares.