Sums of Sums of ... Sums of Powers stuff -- How to Construct ANY formula: (This document MUST be viewed in a fixed-pitched font) m=0: sequences of n^0, some sums, and result of inflicting "finite differences" on them: n=0 n=1 n=2 n=3 n=4 n=5 n=6 / / / / / / / + 1 3 6 10 15 21 28 (0D) (sums of sums, or sums_2) + 1 2 3 4 5 6 7 (0C) (sums) 1* 1 1 1 1 1 1 (0B) (zeroths) - 0 0 0 0 0 0 (0A) (differences) *(NEED to assign zero-raised-to-power-zero as 1, for consistency) m=1: sequences of n^1, their sums, and result of inflicting "finite differences" on them: n=0 n=1 n=2 n=3 n=4 n=5 n=6 / / / / / / / + 0 1 3 6 10 15 21 (1D) (sums) 0 1 2 3 4 5 6 (1C) (firsts) - 1 1 1 1 1 1 (1B) (differences) - 0 0 0 0 0 (1A) (diffs of diffs, or diffs_2) (Please note the 1 at left, for later use) m=2: sequences of n^2, their sums, and result of inflicting "finite differences" on them: n=0 n=1 n=2 n=3 n=4 n=5 n=6 / / / / / / / + 0 1 5 14 30 55 91 (2E) (sums) 0 1 4 9 16 25 36 (2D) (squares) - 1 3 5 7 9 11 (2C) (differences) - 2 2 2 2 2 (2B) (diffs_2) - 0 0 0 0 (2A) (diffs_3) (Please note the 1 and 2 at left, for later use) m=3: sequences of n^3, their sums, and result of inflicting "finite differences" on them: n=0 n=1 n=2 n=3 n=4 n=5 n=6 / / / / / / / + 0 1 9 36 100 225 441 (3F) (sums) 0 1 8 27 64 125 216 (3E) (cubes) - 1 7 19 37 61 91 (3D) (differences) - 6 12 18 24 36 (3C) (diffs_2) - 6 6 6 6 (3B) (diffs_3) - 0 0 0 (3A) (diffs_4) (Please note the 1 and 6 and 6 at left, for later use) m=4: sequences of n^4, their sums, and result of inflicting "finite differences" on them: n=0 n=1 n=2 n=3 n=4 n=5 n=6 / / / / / / / + 0 1 17 98 354 979 2275 (4G) (sums) 0 1 16 81 256 625 1296 (4F) (fourths) - 1 15 65 175 369 671 (4E) (differences) - 14 50 110 194 302 (4D) (diffs_2) - 36 60 84 108 (4C) (diffs_3) - 24 24 24 (4B) (diffs_4) - 0 0 (4A) (diffs_5) (Please note the 1 and 14 and 36 and 24 at left, for later use) ------------------------------------------------------------------------------------ Now for the formulas, deliberately made overly complex to show the patterns: Rows 0A, 1A, 2A, etc. show that enough "finite differences" of powers result in zero. (Naturally, taking any further differences will still yield zero.) Row 0B = (0!) *(NEED to assign zero-raised-to-power-zero as equal to factorial 0) Row 1B = (1!) Row 2B = (2!) Row 3B = (3!) Row 4B = (4!) Apparently, Row mB = (m!) Row 0C = (0)/(0!) + (0!)(n+1)/(1!) (sums of zeroths) Row 1C = (0)/(0!) + (1!)(n+0)/(1!) (firsts) Row 2C = (1)/(0!) + (2!)(n-1)/(1!) (first differences between squares) Row 3C = (6)/(0!) + (3!)(n-2)/(1!) (diffs_2 of cubes) Row 4C = (36)/(0!) + (4!)(n-3)/(1!) (diffs_3 of fourths) Apparently, Row mC = (LC) /(0!) + (m!)(n-(m-1))/(1!) where LC is leftmost value in row C. (Naturally, the constant (m!) is also always LB, the leftmost value in its own row B.) Row 0D = (0)/(0!) + (0)(n+2)/(1!) + (0!)(n+1)(n+2)/(2!) (sums_2 of zeroths) Row 1D = (0)/(0!) + (0)(n+1)/(1!) + (1!)(n+0)(n+1)/(2!) (sums of firsts) Row 2D = (0)/(0!) + (1)(n+0)/(1!) + (2!)(n-1)(n+0)/(2!) (squares) Row 3D = (1)/(0!) + (6)(n-1)/(1!) + (3!)(n-2)(n-1)/(2!) (1st diffs of cubes) Row 4D = (14)/(0!) + (36)(n-2)/(1!) + (4!)(n-3)(n-2)/(2!) (diffs_2 of fourths) Apparently, row mD = (LD) /(0!) + (LC) (n-(m-2))/(1!) + (m!)(n-(m-1))(n-(m-2))/(2!) Row 0E = (0)/(0!) + (0)(n+3)/(1!) + Row 1E = (0)/(0!) + (0)(n+2)/(1!) + Row 2E = (0)/(0!) + (0)(n+1)/(1!) + Row 3E = (0)/(0!) + (1)(n+0)/(1!) + Row 4E = (1)/(0!) + (14)(n-1)/(1!) + (0)(n+2)(n+3)/(2!) + (0!)(n+1)(n+2)(n+3)/(3!) (sums_3 of zeroths) (0)(n+1)(n+2)/(2!) + (1!)(n+0)(n+1)(n+2)/(3!) (sums_2 of firsts) (1)(n+0)(n+1)/(2!) + (2!)(n-1)(n+0)(n+1)/(3!) (sums of squares) (6)(n-1)(n+0)/(2!) + (3!)(n-2)(n-1)(n+0)/(3!) (cubes) (36)(n-2)(n-1)/(2!) + (4!)(n-3)(n-2)(n-1)/(3!) (1st diffs of fourths) Apparently, row mE = (LE) /(0!) + (LD) (n-(m-3))/(1!) + (LC) (n-(m-2))(n-(m-3))/(2!) + (m!)(n-(m-1))(n-(m-2))(n-(m-3))/(3!) Row 0F = (0)/(0!) + (0)(n+4)/(1!) + (0)(n+3)(n+4)/(2!) + Row 1F = (0)/(0!) + (0)(n+3)/(1!) + (0)(n+2)(n+3)/(2!) + Row 2F = (0)/(0!) + (0)(n+2)/(1!) + (0)(n+1)(n+2)/(2!) + Row 3F = (0)/(0!) + (0)(n+1)/(1!) + (1)(n+0)(n+1)/(2!) + Row 4F = (0)/(0!) + (1)(n+0)/(1!) + (14)(n-1)(n+0)/(2!) + (0)(n+2)(n+3)(n+4)/(3!) + (0!)(n+1)(n+2)(n+3)(n+4)/(4!) (sums_4 of zeroths) (0)(n+1)(n+2)(n+3)/(3!) + (1!)(n+0)(n+1)(n+2)(n+3)/(4!) (sums_3 of firsts) (1)(n+0)(n+1)(n+2)/(3!) + (2!)(n-1)(n+0)(n+1)(n+2)/(4!) (sums_2 of squares) (6)(n-1)(n+0)(n+1)/(3!) + (3!)(n-2)(n-1)(n+0)(n+1)/(4!) (sums of cubes) (36)(n-2)(n-1)(n+0)/(3!) + (4!)(n-3)(n-2)(n-1)(n+0)/(4!) (fourths) Apparently, row mF = (LF) /(0!) + (LE) (n-(m-4))/(1!) + (LD) (n-(m-3))(n-(m-4))/(2!) + (LC) (n-(m-2))(n-(m-3))(n-(m-4))/(3!) + (m!)(n-(m-1))(n-(m-2))(n-(m-3))(n-(m-4))/(4!) Row 0G = (0)/(0!) + (0)(n+5)/(1!) + (0)(n+4)(n+5)/(2!) + (0)(n+3)(n+4)(n+5)/(3!) + Row 1G = (0)/(0!) + (0)(n+4)/(1!) + (0)(n+3)(n+4)/(2!) + (0)(n+2)(n+3)(n+4)/(3!) + Row 2G = (0)/(0!) + (0)(n+3)/(1!) + (0)(n+2)(n+3)/(2!) + (0)(n+1)(n+2)(n+3)/(3!) + Row 3G = (0)/(0!) + (0)(n+2)/(1!) + (0)(n+1)(n+2)/(2!) + (1)(n+0)(n+1)(n+2)/(3!) + Row 4G = (0)/(0!) + (0)(n+1)/(1!) + (1)(n+0)(n+1)/(2!) + (14)(n-1)(n+0)(n+1)/(3!) + (0)(n+2)(n+3)(n+4)(n+5)/(4!) + (0!)(n+1)(n+2)(n+3)(n+4)(n+5)/(5!) (sums_5 zeroths) (0)(n+1)(n+2)(n+3)(n+4)/(4!) + (1!)(n+0)(n+1)(n+2)(n+3)(n+4)/(5!) (sums_4 firsts) (1)(n+0)(n+1)(n+2)(n+3)/(4!) + (2!)(n-1)(n+0)(n+1)(n+2)(n+3)/(5!) (sums_3 squares) (6)(n-1)(n+0)(n+1)(n+2)/(4!) + (3!)(n-2)(n-1)(n+0)(n+1)(n+2)/(5!) (sums_2 cubes) (36)(n-2)(n-1)(n+0)(n+1)/(4!) + (4!)(n-3)(n-2)(n-1)(n+0)(n+1)/(5!) (sums_1 fourths) Apparently, row mG = (LG) /(0!) + (LF) (n-(m-5))/(1!) + (LE) (n-(m-4))(n-(m-5))/(2!) + (LD) (n-(m-3))(n-(m-4))(n-(m-5))/(3!) + (LC) (n-(m-2))(n-(m-3))(n-(m-4))(n-(m-5))/(4!) + (m!)(n-(m-1))(n-(m-2))(n-(m-3))(n-(m-4))(n-(m-5))/(5!) ------------------------------------------------------------------------------------ From the preceding, we might consider a grand generalization: Let m be the chosen power and n be the chosen last number in the sequence 1, 2, 3, ..., n and p be the chosen "level" of summation or differences, thusly: ... (pre cetera) p=+3 sums of sums of sums of n items of power m p=+2 sums of sums of n items of power m p=+1 sums of n items of power m p= 0 the n items of power m p=-1 differences between items of power m p=-2 differences between differences between items of power m p=-3 diffs between diffs between diffs between items of power m ... (et cetera) THEN: A sequence of (m+p+1) terms must be created and added together. Each term can have the simple form of (X)(Y), where (X) is a numerical coefficient, and (Y) is a variable expression. We examine some of the (X) values first: The numbers in each row of this triangular arrangement come (in "Please Note"s above) from multiple levels of simple subtraction between the numbers zero through m, after they are raised to the mth power. Results from the 1st through 7th powers are tabulated here: m=1 1 m=2 1 2 m=3 1 6 6 m=4 1 14 36 24 m=5 1 30 150 240 120 m=6 1 62 540 1560 1800 720 m=7 1 126 1806 8400 16800 15120 5040 (Imagine an infinity of invisible zeros at left, right, and top). This table can be simplified! From upper-right to lower-left, each diagonal row contains numbers all of which are exactly divisible by the upper-right-most number (which is a factorial). Extracting the factorials means that the previously-described terms (X)(Y) can now be rewritten as (X)(Y)(Z!), using this new table for the (X) values: m=1 1 m=2 1 1 m=3 1 3 1 m=4 1 7 6 1 m=5 1 15 25 10 1 m=6 1 31 90 65 15 1 m=7 1 63 301 350 140 21 1 The numbers in this table can be computed, each from the pair of numbers directly above it (including invisible zeros). Let the left-most diagonal row be assigned a Coordinate or (Z) value of One, and the next diagonal row be assigned a Coordinate or (Z) value of Two, and so on. Multiply any number by its (Z) value, and add in its neighbor on the left, to obtain the number below that pair. For example, the 15 in the sixth horizontal row has a (Z) value of Five, so: (5 * 15) + 65 = 140. Obviously, if any (X) value in this table is multiplied by the factorial of its Coordinate or (Z) value, the equivalent (X) value in the prior table will be generated. Next, we need a generic way to describe the (Y) expressions, which is appropriately relevant to the desired result. From inspection of all those complicated formulas, and the definition of p, we will find that: (Y1) = 1/(0!) (can't avoid that '1' here, normally (X)) (Y2) = (Y1) * (n+p )/1 (note 0! * 1 yields 1! in denominator) (Y3) = (Y2) * (n+p-1)/2 (Y4) = (Y3) * (n+p-2)/3 (Y5) = (Y4) * (n+p-3)/4 et cetera It is kind of nice that no matter how complicated a (Y) expression appears to be (in that original list of formulas), each one can be derived quite simply from the previous one. Since we know we need to add up m+p+1 expressions, we can easily write a program to use some of the results of each step, in figuring the results of the next step -- no need to create and evaluate a lot of huge expressions from scratch! Also, should any one of these (Y) expressions evaluate to zero, then the program can stop generating them altogether, because all following expressions will also be zero. (This generally happens whenever n < m) Now all we have to do is note how to associate those (X) values with appropriate (Y) expressions. In one sense, this also is simple: The quantity-m of the (X) values in row m of the triangular table will exactly associate FROM RIGHT TO LEFT with the LAST quantity-m (Y) expressions. In other words, consider this formula copied from above: Row 4D = (14)/(0!) + (36)(n-2)/(1!) + (4!)(n-3)(n-2)/(2!) (diffs_2 of fourths) In this formula, m=4 and p=-2, so (m+p+1)=3 terms to add together. Even though there are 4 (X) values in the mth row of the (first) triangular table, only the rightmost 3 of them are used here, and they are associated from right to left with the (Y) expressions. Meanwhile, in this other formula copied from above: Row 1D = (0)/(0!) + (0)(n+1)/(1!) + (1!)(n+0)(n+1)/(2!) (sums of firsts) Here m=1 and p=+1, so again (m+p+1)=3 terms to add together. And the single (X) value on the m=1 row of the triangular table is associated with the last/rightmost (Y) expression. The zeros associated with the first two terms come from the invisible surroundings of the triangular tables, and because they are needed here, this is why they were mentioned previously. The preceding simplicity now is dealt the annoyance that we will most probably compute the (Y) expressions from the easiest and leftmost term (previously designated as (Y1)), so we need a guide to determining exactly WHICH (X) value on a left-to-right basis, to associate with a given (Y) expression. On the other hand, the preceding descriptions pretty much answer that question with the calculation of (m+p+1)-m. That obviously simplifies to p+1, and this is how many zeros are needed to the left of the first (X) term on the mth horizontal row of the triangular table. As you can see from the copied Row 1D, p=+1, and p+1=2, and there are indeed two preceding zeros. Meanwhile, in Row 4D p=-2, and p+1=-1, a result that matches the fact that just one (the first) (X) value on the m=4 horizontal row was not used. So there you have it: A general procedure for contructing any formula to compute any level of sums or differences of powers. (Not to mention, merely changing the (X) values can let this overall procedure become associated with ANY OTHER regular series of numbers that can be dissected by "finite differences"....) Enjoy! Vernon Nemitz