In today's blog, I will first use induction to prove the summation formulas for ∑ x, ∑ x2, and
∑ x3. Then, I will show how it is possible to derive each of these formulas.
I will use the summation formula ∑ x3 in my example of using a Riemann sum to calculate the area under a simple curve.
Lemma 1:
(a) (n-1)2 = n2 - 2n + 1
(b) (n-1)3 = n3 - 3n2 + 3n - 1
(c) (n-1)4 = n4 -4n3 + 6n2 -4n + 1
Proof:
(a) This follows straight from multiplying (n-1)(n-1)
(b) (n-1)3 = (n-1)(n2 - 2n + 1) = n3 - 2n2 + n -n2 + 2n - 1 = n3 - 3n2 + 3n - 1
(c) (n-1)4 = (n-1)(n3 - 3n2 + 3n - 1) = n4 -3n3 + 3n2 - n -n3 +3n2 -3n + 1 = n4 -4n3 + 6n2 -4n + 1
QED
Lemma 2: ∑(i=1,n) i = (1/2)n2 + (1/2)n
Proof:
(1) ∑ (i=1,1) i = 1 = (1/2)(1) + (1/2)(1) = 1
(2) Since this is true for n=1, let's assume it's true up to n-1.
(3) Then ∑ (i=1,n) i = ∑(i=1,n-1)i + n = (1/2)(n-1)2 + (1/2)(n-1) + n = (1/2)(n2 - 2n + 1) + (1/2)(n) - (1/2) + n = (1/2)n2 + (1/2)n
(4) Which proves its true by mathematical induction.
QED
Corollary 2.1: ∑(i=1,n) i = (1/2)n(n+1)
Proof:
(1) From Lemma 2, we have:
∑(i=1,n) i = (1/2)n2 + (1/2)n
(2) (1/2)n2 + (1/2)n = (1/2)[n2 + n] = (1/2)[n(n + 1)]
QED
Lemma 3: ∑ (i=1,n) i2 = (1/3)n3 + (1/2)n2 + (1/6)n
Proof:
(1) ∑ (i=1,1) i 2 = 1 = (1/3)(1) + (1/2)(1) + (1/6)(1) = 1
(2) Since this is true for n=1, let's assume it's true up to n-1.
(3) Then ∑(i=1,n) i2 = ∑(i=1,n-1)i2 + n2 = (1/3)(n-1)3 + (1/2)(n-1)2 + (1/6)(n-1) + n2
(4) Applying lemma 1 above gives us:
(1/3)(n-1)3 + (1/2)(n-1)2 + (1/6)(n-1) = (1/3)(n3 - 3n2 + 3n - 1) + (1/2)(n2 - 2n + 1) + (1/6)n - (1/6) + n2 = (1/3)n3 -n2 +n - (1/3) + (1/2)n2 -n + (1/2) + (1/6)n - (1/6) + n2 = (1/3)n3 + (1/2)n2 + (1/6)n
(5) Which proves its true by mathematical induction.
QED
Lemma 4: ∑ (i=1,n) i3 = (1/4)n4 + (1/2)n3 + (1/4)n2
Proof:
(1) ∑ (i=1,1) i3 = 1 = (1/4)(1) + (1/2)(1) + (1/4)(1) = 1
(2) Since this is true for n=1, let's assume it's true up to n-1.
(3) Then ∑ (i=1,n) i3 = ∑(i=1,n-1)i3 + n3 = (1/4)(n-1)4 + (1/2)(n-1)3 + (1/4)(n-1)2 + n3
(4) Applying lemma 1 above gives us:
(1/4)(n-1)4 + (1/2)(n-1)3 + (1/4)(n-1)2 + n3 = (1/4)(n4 -4n3 + 6n2 -4n + 1) + (1/2)( n3 - 3n2 + 3n - 1) + (1/4)(n2 - 2n + 1) + n3 =
= (1/4)n4 + (1/2)n3 + (1/4)n2
(5) Which proves its true by mathematical induction.
QED
I now present a method for deriving each of these formulas. The content in this section is taken from Boris Spokoinyi's web site (see references below)
Example 1: ∑ i = (1/2)n2 + (1/2)n
This formula comes from Carl Friedrich Gauss. The story goes that he came up with it when he was a young schoolboy. He was told to add up all the numbers from 1 to 100. Gauss came up with the formula and calculated the sum in less than five minutes.
(1) The sum = 1 + 2 + 3 + 4 + 5 + ...
(2) If we line this up with n going the other way we have:
1 + 2 + 3 + 4 + 5 + ....
n + (n-1) + (n-2) + ....
So that we have (1 + n) + (2 + n - 1) + (3 + n - 2) + ...
(3) This means that addition of the two sums ∑ (i=1,n) (n)*2 = (n)(n+1) and dividing both sides by 2 gives us:
∑ (i=1,n) (n) = (1/2)(n)(n+1) = (1/2)(n2 n) = (1/2)n2 + (1/2)n.
Example 2: ∑ (i=1,n) i2
(1) ∑ (i=1,n) (i+1)3 = ∑ (i=1,n)(i3 + 3i2 + 3i + 1)
(2) ∑ (i=1,n)(i3 + 3i2 + 3i + 1) = ∑ (i=1,n) i3 + 3∑(i=1,n) i2 + 3∑(i=1,n) i + ∑ (i=1,n) 1
(3) From Lemma 2 (see Example 1 for deriving it), we have:
∑ (i=1,n) i = (n)(n+1)/2
(4) ∑ (i=1,n) 1 = 1 + 1 + ... + 1 = n
(5) Applying step #3 and step #4 to step #2 gives us:
∑ (i=1,n) i3 + 3∑(i=1,n) i2 + 3∑(i=1,n) i + ∑ (i=1,n) 1 = ∑ (i=1,n) i3 + 3∑(i=1,n) i2 + 3(n)(n+1)/2 + n
(6) ∑(i=1,n) (i+1)3 = ∑ (i=2,n+1) i3 = ∑ (i=1,n) i3 + (n+1)3 - 13
(7) So that combining step #5 and step #6 gives us:
∑ (i=1,n) i3 + 3∑(i=1,n) i2 + 3(n)(n+1)/2 + n = ∑ (i=2,n+1) i3 = ∑ (i=1,n) i3 + (n+1)3 - 1
After subtracting ∑ (i=1,n) i3 from both sides, we get:
3∑(i=1,n) i2 + 3(n)(n+1)/2 + n = (n+1)3 - 1
(8) Subtracting 3(n)(n+1)/2 + n from both sides gives us:
3∑(i=1,n) i2 = (n+1)3 - 1 - 3(n)(n+1)/2 -n
So that we have:
∑(i=1,n) i2 = (1/3)[(n+1)3 - 1 - 3(n)(n+1)/2 -n]
(9) Since (n+1)3 = n3 + 3n2 + 3n + 1, we have:
(1/3)[(n+1)3 - 1 - 3(n)(n+1)/2 -n] = (1/3)[n3 + 3n2 + 3n + 1 - 1 - (1/2)3n2 - (1/2)(3n) - n] =
= n3/3 + n2/2 + n/6
Example 3: ∑ (i=1,n) i3
(1) Since (i+1)4 = (i4 + 4i3 + 6i2 + 4i + 1), we have:
∑ (i=1,n) (i+1)4 = ∑ (i=1,n) (i4 + 4i3 + 6i2 + 4i + 1) =
= ∑ (i=1,n) i4 + 4∑(i=1,n)i3 + 6∑(i=1,n)i2 + 4∑(i=1,n)i + ∑(i=1,n)1
(2) Likewise, we have:
∑ (i=1,n) (i+1)4 = ∑ (i=2,n+1) i4 = ∑ (i=1,n) i4 + (n + 1)4 - 14
(3) So that we get:
∑ (i=1,n) i4 + 4∑(i=1,n)i3 + 6∑(i=1,n)i2 + 4∑(i=1,n)i + ∑(i=1,n)1 = ∑ (i=1,n) i4 + (n + 1)4 - 1
And subtracting ∑ (i=1,n) i4 from both sides gives us:
4∑(i=1,n)i3 + 6∑(i=1,n)i2 + 4∑(i=1,n)i + ∑(i=1,n)1 = (n + 1)4 - 1
(4) Which means that:
∑ (i=1,n)i3 = (1/4)[(n + 1)4 - 1 - 6∑(i=1,n)i2 - 4∑(i=1,n)i - ∑(i=1,n)1]
(5) Now, we know that:
∑ (i=1,n) = n
∑ (i=1,n)i = (1/2)n2 + (1/2)n [See Lemma 2 above and Example 1 above]
∑ (i=1,n) i2 = (1/3)n3 + (1/2)n2 + (1/6)n [See Lemma 3 above and Example 2 above]
(4) So that we have:
∑ (i=1,n)i3 = (1/4)[(n + 1)4 - 1 - 6(1/3)n3 - 6(1/2)n2 - (6)(1/6)n - 4(1/2)n2 - 4(1/2)n - n] = (1/4)[n4 + 4n3 + 6n2 + 4n + 1 - 1 -2n3 -3n2 -n -2n2 -2n -n] =
= (1/4)[n4 + 2n3 + n2] = (1/4)n4 + (1/2)n3 + (1/4)n2
References
- Boris Spoloinyi, Summation Formulas
14 comments :
Thanks dude
I an unsure if the summation formula is what I am looking for, but I am sure you've heard of doubling the penny scenario where 1 penny is doubled every day for X days and each day is added. What is the simple formula for this type of problem and also the name of it.
NPeltchie1@aol.com
That's 1 + 2 + 4 + ... 2^n
That's called a geometric series.
Here's a wikipedia article on
it:
Here's your answer:
sum = [1 - 2^(n+1)]/(1 - 2) = -[1 - 2^(n+1)] = 2^(n+1) - 1
For n=1, the value is 2^(2) - 1= 3 = 1 + 2
For n=2, the value is 2^(3)-1 = 7 = 1 + 2 + 4
And so on...
Check the Wikipedia article for more details if needed.
-Larry
Hi Larry,
I'm trying to figure out the formula for a specific problem. I'll do my best to explain.
Say you have each letter of the alphabet written onto small bits of paper, and you put all 26 pieces into a bag. What is the likelihood you will draw the letter A? 1/26, right? What about if you discard your first pick if it is not the A, then draw again? 1/25, right? Now what if I tell you that you will start with the entire alphabet in the bag, but will get two attempts? What will your odds be? 1/26 + (1/25 X 25/26) right?
You can see that gets pretty convoluted after just a few picks. I would like to be able to know exactly what my odds are were I to start out with a full bag of letters, and adjust the variables... the variables being A: how many picks I get and B: how many of the letters I can pick. For example, if 26 letters are in a bag, what are the odds that you will pick the letters A, B, C, or D given 7 picks, discarding each letter after it has been pick, thus reducing the field.
Let me know if you can help, thank.
elkingrey@yahoo.com
Hi,
If I understand your question right, then you are interested in figure out combinatorics.
How many ways are there to pick a,b out of n tries of selecting from a bag of x.
I've already written a blog on combinatorics which you can find here.
Please let me know if that doesn't answer your question.
-Larry
I have a math problem I can't seem to find the formula for. I believe I know how to work it out but maybe you would know the initial formula. My problem is a proof and it ∑i^4 (where n is above the ∑ and i=1 is below it) and my problem is to proof that = (n(n+1)(2n+1)(3n^2 + 3n - 1)) / 30 using mathemaical induction. Any ideas? Thanks!
"Begging the question" is a logical fallacy. You mean "[it] _raises_ the question..."
Hi Anonymous,
I'm not sure why "begging the question" is a logical fallacy.
It's an English idiom.
I agree with you that "raises the question" is a clearer statement of my point.
Cheers,
-Larry
Hi
I have a question...
On a cantilever bar of length 'l' a load is acting, which is uniformly increased from 0 (zero) to W. Increase of weight per unit length is W/l.
Suppose at a point of 'X' the load on both side is equal, meanc 'X' is the center of load then summation of load of both side is equal...I want the formula to find out the summation of loads on both side.
"Begs the question" means to incorrectly assume as true. It's not the same thing as "raises the question."
I must admit that I didn't realize that the phrase "begs the question" has a precise logical meaing.
I've changed my wording to "raises the question".
Thanks for the correction! :-)
-Larry
Hi, I have a question and ill try to explain the best I can.
So there is a 10 story building. This ten story builiding is made out of cubes, and I'm just giving you the info on how it looks so this isn't really that much important. Ok so the last floor is always going to be one because it's the highest point and its made out of only one cube.
When you go down to the 9nth floor, the number of cubes increases to 9, or 3 squared. When you go to the 8th floor, it is then 25 cubes, or 5squared. When you go down to the 7th floor its 49 cubes, or 7squared. Do you see the pattern?
So I am trying to find out a summation formula to find out how many cubes are not showing in total. A formula for finding out the total number of cubes. And an overall formula to find out the total number of cubes with only 2 sides showing.
I have the information I just need the formulas so here is the info.
Total number of bricks=
1st story= 19squared=361
2nd story= 17squared=289
3rd story= 15squared= 225
4th story= 13squared=169
5th story= 11squared=121
6th story=9squared=81
7th story=7squared=49
8th story=5squared=25
9th story=3squared=9
10th story=1squared=1
See the patterns...
I also need to kno the way to find the total number of cubes not showing at all so I'm going to start from the 1st floor and go down with the info.
289=17squared
225=15squared
169=13squared
121=11squared
81=9squared
49=7squared
25=5squared
9=3squared
1=1squared
0= 0
They are in order from the 1st story to the 10nth story. So I need to find a formula for both of those. And if you can for the total number of cubes with 2 sides showing only.
thanx for the summation formulae
Post a Comment