About 1974 I was browsing through a library, and happened to encounter a "Handbook of Mathematics". Most of the stuff in such a book is over my head, but some of it isn't, and some of it my head's range might grow into, if only I looked at it. So I looked.
One page hooked my interest. It contained a list of ten mathematical formulae, making it reasonably easy to compute such things as:
1-squared plus 2-squared plus 3-squared plus ... plus n-squared.
OR:
1-to-the-5th-power plus 2-to-the-5th-power plus ... plus n-to-the-5th-power.
OK, so here were these ten different formulae, containing a number of similarities, for the first ten Sums of Powers. WHY WASN'T THERE A GENERAL FORMULA?
I put the book away, and gave myself the task of finding one. Yes, I know there's no accounting for one's taste in pastimes! I passed about 5 years of time, twiddling on and off (mostly off; less than two months of actual work went into it). I succeeded! Twice! Now to tell people!
Screeching halt: Shortly after my success, I happened to encounter another Handbook of Mathematics. (I couldn't re-visit the original, because I had moved 2000 miles during those five years.) This book HAD a general formula already in it!!! On the next page! I had put it away too quickly!
But the formula in the book looked different from the ones I had derived....
There WAS an overall similarity. What I had actually worked out was a procedure for generating an individual formula for any ONE power m, which could sum up n items, each-raised-to-the-mth-power. It was because I didn't like that idea -- I wanted one single formula -- that I kept at the problem...and instead found a second procedure for generating any individual formula. <THAT> was when I quit.
Well, the thing in the Handbook was ALSO a procedure for generating any individual formula! So maybe the ideal that I had wanted simply wasn't possible. OK.
The procedure in the Handbook was also a lot more complicated-looking than either of mine. The Handbook even SAID that generating an individual formula was a difficult task.
WRONGO! So I still had a chance to publish the results of my efforts. I thought.
Over the years I sent it off to various places, and nothing, to my knowledge, ever came of it. But now I have access to a great place to post ideas, known as the HalfBakery....
--------------------------
The goal is to compute 1-to-the-mth-power plus 2-to-the-mth-power plus 3-to-the-mth-power plus ... plus n-to-the-mth-power.
Both procedures specify a group of mathematical expressions that must be summed up. The NUMBER of these expressions is equal to m. So if the mth-power is 2000, then there will be 2000 expressions to formulate, compute individually, and to then summate.
In one of my procedures, every expression has two parts that are multiplied together. In the other, every expression has three parts that are multiplied together. I'll describe the two-part-expression procedure first:
(X1)(Y1) + (X2)(Y2) + (X3)(Y3) + ... + (Xm)(Ym)
The Xs are simply numerical coefficients. They are derived from a special table; the numbers in that table are reasonably easy to compute. The table is triangular in shape; the uppermost row has 1 value on it (for use when m=1), the second row has 2 values on it (for use when m=2), and so on. So, if m=2000, then we need the 2000 numbers located on the 2000th row of the table. There IS a drawback here: So far as I know, we can't directly compute the numbers on the 2000th row; we can only figure them out by computing all 1999 prior rows first! Here is the first part of this table:
______________________1
__________________1_______1
______________1______4________1
_________1_______11______11_______1
______1______26______66______26______1
___1_____57_____302_____302______57_____1
1____120____1191____2416____1191____120____1
To compute numbers in this table, use this procedure: First lay down diagonal lines to create a grid of rhomboids, each rhomboid contains one of the numbers. Next, OUTSIDE the table, enumerate the grid: Along the leftmost diagonal, the uppermost '1' is #1, the next '1' is #2, and so on. Do the same for the rightmost diagonal. Thus every number in the table has a pair of "diagonalized" coordinates. (The first '26' in the fifth horizontal row has left-diagonal coordinate of 4 and a right-diagonal coordinate of 2, for example.) Obviously, every number NOT YET in the table also has an equivalent pair of coordinates. Before getting to that, however, please note that every number in the table, except for the outermost '1's, has a pair of numbers offset above it in the previous row. (For example, the first 1191 in the seventh row has 57 and 302 above it.) Finally, take the coordinates of a number, AND the two numbers above it, and use them to compute the number: Since the coordinates of that 1191 are 5 and 3, (57*5)+(302*3)=1191. Similarly, if the first 120 and 1191 in the seventh row are combined with the coordinates of the number below them in the eighth row, we will compute: (120*6)+(1191*3)=4293. Since it is the third number in the eighth horizontal row, that 4293 WILL BE (X3) when m=8.
Now for the Ys in the procedure. Y1 is this:
(m+n)! / (m+1)! * (n-1)!
The exclamation marks specify "factorial" values, so if (m+n)=10, then (m+n)!=10!=1*2*3*4*5*6*7*8*9*10. One of the cool things about factorials in formulae like this is that it is so easy to cancel out a lot of terms, BEFORE multiplying to find the result. For example, if m=2000 and n=4, then the actual computation will be: (2002*2003*2004)/(1*2*3). It should also be noted that 0! (factorial of zero) is DEFINED as being equal to ONE. (There are lots of formulae where something like that (n-1)! above may be converted into 0! --and in the denominator of a fraction, it MUST be a valid value....)
When preparing to use this overall procedure in a computer program, the numerical value of Y1 should be figured before proceding to Y2. The reason for that is:
(Y2)=(Y1)(n-1)/(m+n)
By simple inspection, the n-1 and m+n are easy values to compute. So it is easier to compute Y2 from the numerical value of Y1, than to create a more complicated expression first, and THEN calculate the result.
Furthermore: (Y3)=(Y2)(n-2)/(m+n-1)
And: (Y4)=(Y3)(n-3)/(m+n-2)
And: (Y5)=(Y4)(n-4)/(m+n-3)
And so on, until the last item in the sequence has been computed. WHILE figuring the next 'Y' item, it wouldn't hurt to be computing (X1)(Y1) + (X2)(Y2) + ... in the background, to get the grand total.
-----------------------------------
The other procedure is actually a little easier to work with than the one just described. I LIKE the previous procedure because of its symmetrical table of X-values, but because this one (the first one I discovered) IS easier to use, the second one will probably fall by the wayside. Ah, well.
As previously mentioned, the overall procedure involves a series of expressions that are added together, each of which consists of three parts that are multiplied together. In greater detail:
(X1)(Y1)(1!) + (X2)(Y2)(2!) + (X3)(Y3)(3!) + ... + (Xm)(Ym)(m!)
Now if you wonder about this really being easier to work with than the previous version, that didn't have the factorials as you see here, well.... First, the (X) and (Y) terms are easier to compute here. Second, since a chain of values must be computed, and the sequences of factorials is perfectly regular, it follows that to compute the current/nth factorial, just start with the previously-computed factorial and multiply by n. In the end, about the same total amount of calculations have to be done, to get the answer, no matter what formula you use. And since we let computers do the grunt-work of calculation these days, what matters is, "Which is easier to program?"
As before, the (X) values come from the horizontal rows of a triangular table:
______________1_______3_______1
_________1________7_______6_______1
______1______15______25______10______1
___1_____31______90______65______15_____1
1_____63_____301_____350_____140_____21____1
While the previous table needs a coordinate system along both outermost diagonals, this table needs coordinates only along the right-side diagonal. Thus the 140 in the seventh horizontal row has a coordinate of 5, while the 90 in the sixth row has a coordinate of 3. As in the previous table, each number (except the outer 1s) is computed from the two numbers above it, but this time only including the one coordinate. Therefore: 31+(90*3)=301, 6+(1*4)=10, 65+(15*5)=140, and so on.
Like the other table, it appears that the only way to compute the numbers on the 2000th row is to first compute all the numbers on the 1999 prior rows. I spent a considerable amount of time seeking a way to avoid having to do that, but failed. Still, with computers to do the grunt-work these days, it's not really such a difficult thing to compute however-many rows are desired. I once programmed my Color Computer (with 8-bit processor) to compute the first 128 rows (as many as I could fit on a floppy disk at the time), and it didn't take all that long.
Next, the first of the (Y) terms is:
(Y1) = n(n+1) / 2
This IS the standard formula, all by itself, for any Sum of First powers: 1+2+3+4+5+...+n. (Note that since X1=1 and 1!=1, those pieces of the overall procedure have no effect.) In fact, if you set m=1 and start with the OTHER (Y1) term, you can algebraically mold it into this (Y1) term here.
As before, it is best to compute (Y1) first, and then use the result in the computation of (Y2):
(Y2) = (Y1)(n-1) / 3
(Y3) = (Y2)(n-2) / 4
(Y4) = (Y3)(n-3) / 5
And so on, for a total of m expressions, as already stated.
In closing, I confess I don't know how many places there are, where either of these procedures can be useful. Nevertheless, I do hope I have advanced the arts a trifle.-- Vernon, Jul 23 2001 Pascal's Triangle. http://ptri1.tripod.com/ [angel, Jul 23 2001, last modified Oct 21 2004] sums of powers http://ca.google.ya...s%22&y=on&hc=0&hs=0over 500 hits on google [mihali][mihali]: 'the seven wonders of the ancient world' http://uk.google.ya...he+ancient+world%224,310 hits. So what? [angel]how about this one? http://www.mathpage...m/home/kmath279.htmi'm no math expert, but it looks like a general formula to me [mihali, Jul 23 2001, last modified Oct 21 2004] [mihali]: 'the seven wonders of the ancient world' http://uk.google.ya...he+ancient+world%224,310 hits. So what? [angel, Jul 23 2001] how about this one? http://www.mathpage...m/home/kmath279.htmi'm no math expert, but it looks like a general formula to me [mihali, Jul 23 2001] or this one? http://www.uwgb.edu...ecmath/rmpowers.htm [mihali, Jul 23 2001, last modified Oct 21 2004] and here is a discussion about it http://nrich.maths....CH/edited/1632.html [mihali, Jul 23 2001, last modified Oct 21 2004] Gamma function http://home.clara.net/sisa/gamma.htm0! = Gamma(1) = 1 [lubbit, Jul 23 2001, last modified Oct 21 2004] Do you have a day job, Vernon?-- lewisgirl, Jul 23 2001 I'm interested in the notion that factorial zero = 1. I admit that I'm no mathematician, but this is news to me.-- angel, Jul 23 2001 Did you really think this up? I've seen that pyramid some place before ...-- futurebird, Jul 23 2001 'That pyramid' is Pascal's Triangle (see link).-- angel, Jul 23 2001 angel, I can't specify the reason why factorial zero is defined as being equal to one, but it really is.
Also, the "pyramid" in the essay is NOT Pascal's Triangle. There is a superficial resemblance, but on the inside of Pascal's Triangle, every number is simply the sum of the two numbers above it. No multiplication involved, like you see here.
lewisgirl and POYF, I actually work 2 jobs. Which is why I don't have time like I used to, to twiddle so much with ideas. About all I can manage these days is to dig 'em up, more-or-less copy them from typewritten pages into the computer, and post 'em.-- Vernon, Jul 23 2001 Having looked further, I now see that 0! is indeed = 1 as a 'special case'. You live and learn! I realise that *your* 'pyramid' isn't Pascal's Triangle, but the one that [futurebird] has seen before probably is. Have you a full (text) version of this dissertation somewhere? It might be easier to absorb if I print it out.-- angel, Jul 23 2001 angel: if you'd bothered to actually look at those sites, you'd see that a general formula for sums of powers already exists.-- mihali, Jul 23 2001 mihali, which site in particular has the general formula? And, is it really just a procedure such as I describe here, and found in the Handbook? **AND** is it easy to use?-- Vernon, Jul 23 2001 mihali, the link you provided {how about this one} IS a description of the same procedure I found in the Handbook. (In fact, the Handbook had two, because the noted Swiss mathematician Euler had devised an alternate -- yet equivalent -- scheme.)
The key word is PROCEDURE, not formula. At the bottom of the linked page is this statement: "The formulas for the sums of other powers can be derived similarly."
Which is what I was describing here -- a procedure to generate formulae. While Bernoulli's method looks simple, it is an illusion based on the compactness that mathematical expressions can sometimes take. Just read the description that accompanies to see how it is expanded out to something with about as many terms as the concoctions I present here! Not to mention that the table of Bernoulli numbers is (according to the Handbook) not so simple to compute....-- Vernon, Jul 23 2001 // ...factorial zero = 1... //
Factorial is a special case of the Gamma function, which can take any real (complex) number as argument. For integer n, n! = Gamma(n+1) & Gamma(1) = 1.-- lubbit, Jul 24 2001 I can't understand most of your postings, Vernon, but they are always impressive. This one sounds - and here I'm judging only from your prose and not your math - tremendous. I wish I could give you 2 croissants. I hope you keep sharing your ideas.-- cheeselikesubstance, Jul 24 2001 The reason for 0! = 1 can also be thought of from combinatorics, where the factorial function is the number of different ways to rearrange n distinct objects. Hence if you have no object, there is only one way to rearrange it.-- leto, Jul 24 2001 Accroding to the recursive definition of factorial, (n+1)! = (n+1) * n!, which implies that n! = (n+1)! / (n+1). Because 1!=1, 0!=1, Q.E.D.-- nobody, Jul 24 2001 This idea stinks. Boring people writing about a boring subject. Where was the "fun" part of this site again?-- PotatoPete, Jul 25 2001 random, halfbakery