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.Originally Posted by OReilly
---
The key in the the fact that,
$\displaystyle 1+2+...+x=\frac{x(x+1)}{2}$
---
Therefore, that entire sum is,
$\displaystyle \frac{1(2)}{2}+\frac{2(3)}{2}+...+\frac{n(n+1)}{2}$
Thus,
$\displaystyle \sum_{k=1}^{n}\frac{k(k+1)}{2}=\frac{1}{2}\sum_{k= 1}^n k^2+k$
Thus, subdivide the summation,
$\displaystyle \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,
$\displaystyle \frac{1}{2}\cdot \frac{n(n+1)}{2}+\frac{1}{2}\cdot \frac{n(n+1)(2n+1)}{6}$
Simplify,
$\displaystyle \frac{n(n+1)}{4}+\frac{n(n+1)(2n+1)}{12}$
Add, common denominator and add,
$\displaystyle \frac{3n(n+1)+n(n+1)(2n+1)}{12}$
Thus, (factor),
$\displaystyle \frac{n(n+1)(3+2n+1)}{12}$
Simplify again,
$\displaystyle \frac{n(n+1)(2n+4)}{12}$
Simplify again,
$\displaystyle \frac{n(n+1)(n+2)}{6}$
~~~
Just for refernce, the sum of squares formula is,
$\displaystyle \sum_{k=1}^nk^2=\frac{n(n+1)(2n+1)}{6}$
----
I think it is cool that,
$\displaystyle \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.
Hello,OReilly!
TPHacker is absolutely correct . . . Nice job, T.P. !
If we are desperate, we could find the formula "from scratch".
Can someone show me the formula for calculating:
. . . $\displaystyle 1+(1+2)+(1+2+3)+(1+2+3+4)+\hdots$
Crank out a list of the first few sums:
$\displaystyle \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 $\displaystyle f(n)$. .For $\displaystyle n = 1,2,3,\hdots$
. . the function has consecutive values: .$\displaystyle 1\quad4\quad10\quad20\quad56\quad84\;\hdots$
Take differences of consecutive terms: . . $\displaystyle 3\quad6\quad\;10\;\quad15\quad21\;\hdots$
Take differences again: . . . . . . . . . . . . . .$\displaystyle 3\quad\;4\quad\;\;5\quad\;\;6\;\hdots$
Take differences again: . . . . . . . . . . . . . . . $\displaystyle 1\quad\;1\quad\;\:1\;\hdots$
We have a series of constants at the third differences.
. . Hence, $\displaystyle f(n)$ is a third-degree polynomial ... a cubic.
Hence, the function is of the form: .$\displaystyle f(n)\:=\:an^3 + bn^2 + cn + d$
. . and we must determine $\displaystyle a,b,c,d.$
Use the first four values from our list.
$\displaystyle S_1\,=\,1:\;\;a\cdot1^3 + b\cdot1^2 + c\cdot1 + d\:=$ $\displaystyle \:1\quad\;\;\;\Rightarrow\quad\;\; a+b+c+d\;=\;1$
$\displaystyle S_2\,=\,4:\;\;a\cdot2^3 + b\cdot2^2 + c\cdot2 + d \:= \:$ $\displaystyle 4\;\;\;\quad\Rightarrow\quad\; 8a + 4b +2c + d \;= \;4$
$\displaystyle S_3\,=\,10:\;a\cdot3^3 + b\cdot3^2 + c\cdot3 + d \:=$ $\displaystyle \:10\quad\Rightarrow\quad 27a + 9b + 3c + d \;= \;10$
$\displaystyle S_4\,=\,20:\;a\cdot4^3 + b\cdot4^2 + c\cdot4 + d\:=$ $\displaystyle \:20\quad\Rightarrow\quad 64a + 16b + 4c + d \;= \;20$
Now we must solve this system of equations . . . but it's easy!
. . $\displaystyle \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): .$\displaystyle 7a + 2b + c \:= \:3\quad\;\;\;(5)$
Subtract (2) from (3): .$\displaystyle 19a + 5b + c \:= \:6\quad\;(6)$
Subtract (3) from (4): .$\displaystyle 376a + 7b + c \:= \:10\;\;(7)$
Subtract (5) from (6): .$\displaystyle 12a + 2b\:=\:3\;\;(8)$
Subtract (6) from (7): .$\displaystyle 18a + 2b\:=\:4\;\;(9)$
Subtract (8) from (9): .$\displaystyle 6a\,=\,1\quad\Rightarrow\quad \boxed{a = \frac{1}{6}}$
Substitute into (8): .$\displaystyle 12\left(\frac{1}{6}\right) + 2b\:=\:3\quad\Rightarrow\quad \boxed{b = \frac{1}{2}}$
Substitute into (5): .$\displaystyle 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): .$\displaystyle \frac{1}{6} + \frac{1}{2} + \frac{1}{3} + d\:=\:1\quad\Rightarrow\quad \boxed{d = 0}$
Therefore: .$\displaystyle 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:
. . $\displaystyle \sum_{k=1}^n k \;= \;\frac{n(n+1)}{2}$
. . $\displaystyle \sum_{k=1}^n n^2\;=\;\frac{n(n+1)(2n+1)}{6}$
. . $\displaystyle \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: .$\displaystyle (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?
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).Originally Posted by Soroban
---
I have a elegant prove with this rule that,
$\displaystyle a^{(m)}_k=\sum_{k=1}^nk^m$ is always a polynomial sequence.
Consider an infinite sequence,
$\displaystyle 0^m,1^m+0^m,2^m+1^m+0^m,...$
Its diffrence sequence is,
$\displaystyle 0^m,1^m,2^m,3^m,...$
A polynomial sequence of degree $\displaystyle m$ therefore $\displaystyle m$ subtractions are required. In total we used $\displaystyle m+1$ subtractions on our original sequence. Thus there exists a polynomial sequence of degree $\displaystyle m+1$. Furthermore, the first coefficient is $\displaystyle \frac{1}{(m+1)!}$. Based on the fact the constant sequence follows the factorial.
Hello, TPHacker!
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, $\displaystyle \sum^n_{k=1} k^4$, we are expected to know the three "preceding" formulas:
. . $\displaystyle \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}$$\displaystyle k^3\:=\:\frac{n^2(n+1)^2}{4}$
Consider the next-higher power and form: .$\displaystyle k^5 - (k-1)^5$
We have: /$\displaystyle k^5 - (k-1)^5\:=\;5k^4 - 10k^3 + 10k^2 - 5k + 1$
Now let $\displaystyle k \,= \,n,\,n\!-\!1,\,n\!-\!2,\,...\,,\,3,\,2,\,1$ and "stack" the equations.
. . . . $\displaystyle n^5 - (n-1)^5\;=\quad\;\;5n^4\quad -\quad\;\; 10n^3\quad +$ . .$\displaystyle 10n^2\quad\; -\quad\; 5n\quad\; + 1$
$\displaystyle (n-1)^5-(n-2)^5 \;=$ $\displaystyle \:5(n-1)^4 - 10(n-1)^3 + 10(n-1)^2 - 5(n-1) + 1$
$\displaystyle (n-2)^5-(n-3)^5 \;=$ $\displaystyle \:5(n-2)^4 - 10(n-2)^3 + 10(n-2)^2 - 5(n-2) + 1$
. . . . . . $\displaystyle \vdots$ . . . . . . . . . . .$\displaystyle \vdots$ . . . . . . . .$\displaystyle \vdots$ . . . . . . . $\displaystyle \vdots$ . . . . . . . $\displaystyle \vdots$ . . . $\displaystyle \vdots$
. . $\displaystyle 3^5\quad -\quad 2^5 \qquad= \quad\;\;5(3^4)\;\;\; -\;\;\; 10(3^3)$ . $\displaystyle +\;\;\; 10(3^2)\quad -\quad 5(3)\quad + 1$
. . $\displaystyle 2^5\quad -\quad 1^5\qquad = \quad\;\;5(2^4)\;\;\; -\;\;\; 10(2^3)$ . $\displaystyle +\;\;\; 10(2^2)\quad -\quad 5(2)\quad + 1$
. . $\displaystyle 1^5\quad -\quad 0^5 \qquad = \quad\;\;5(1^4)\;\;\; -\;\;\; 10(1^3)$ . $\displaystyle + \;\;\;10(1^2)\quad -\quad 5(1)\quad + 1$
Add the stack (most of the left side cancels out):
. . $\displaystyle n^5\;=\;5\left(\sum k^4\right) - 10\left(\sum k^3\right) +$ $\displaystyle 10\left(\sum k^2\right) - 5\left(\sum k\right) + \left(\sum 1\right)$
We have: .$\displaystyle n^5 \;= \;5\left(\sum k^4\right)-10\cdot\frac{n^2(n+1)^2}{4} +$ $\displaystyle 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:
. . . . $\displaystyle \boxed{\sum^n_{k=1} k^4\;=\;\frac{n(n+1)(2n+1)(3n^2 + 3n - 1)}{30}}$
Quick! . . . Add that to your list!
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.