Sums of Powers

by Vernon Nemitz

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 + 2-to-the-5th-power +...+ 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 (by Bernoulli) looked different from the ones that 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 sum of 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. (I should note that therere was also some reference to some work done by Euler, similar to Bernoulli's.) 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 for a high power 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 the Internet....

------

The goal is to compute 1-to-the-mth-power + 2-to-the-mth-power + 3-to-the-mth-power + ... + 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 add.

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 one value on it (for use when m=1), the second row has two values on it (for use when m=2), and so on. So, if m=2000, then we need the two thousand 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

(The underscores preserve the layout regardless of font.) 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

__________________1_______1

______________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 TRS-80 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. I imagine someone might want to compute several thousand rows and then publish them, just so they never have to be re-computed.

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, from the previous procedure, 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. Most especially do I wonder whether or not ANOTHER procedure awaits discovery, which is directly based on Pascal's Triangle. After all, the first of the two 'triangles' presented here is computed by a combination of two multiplications and an addition, while the second is computed via one multiplication and one addition...and Pascal's Triangle is computed via addition only. If such a procedure for Sums of Powers COULD be found, then we wouldn't have to compute all prior rows to determine the (X) coefficients we need from the mth row; we already have a formula to get them directly. (Still, computing them just once, and tabulating them, does have merit....)

Vernon Nemitz