## Dobbs’s Power Summation Rule January 27, 2010

Posted by eric22222 in General, Math, Personal Favorites.

When an interesting problem comes to mind, class is over for me. I reach a point where “quiz” this and “exam” that are completely overshadowed by some Interesting Problem. Today, during a lecture about countably infinite sets, my mind went back to a previously unsolved problem I had posed to myself last semester. It goes something like this:

We know that the sum of integers from one to N can be found with the formula

$\displaystyle\sum_{x=1}^N x^1 = \frac{N^2 + N}{2}$

So how can we represent the sum of squares? Cubes? Is there a general function for any power? I’ve managed to find a form for the sum of squares:

$\displaystyle\sum_{x=1}^N x^2 = \frac{2{N^3} + 3{N^2 }+ N}{6}$

Furthermore, I can backtrack to get the sum of ones to continue the pattern in both directions:

$\displaystyle\sum_{x=1}^N x^0 = N$

Yes, that is a complicated formula to say you’ll get five if you add five ones together. So given these three formulas, here’s my idea: each formula is a simple polynomial of degree d, where d is one greater than the power each term is raised to. So I can calculate plenty of equations. Let’s make a system of them to calculate the sum of cubes, shall we?

$\left[ \begin{array}{cccc} 1 & 1 & 1 & 1 \\ 2 & 4 & 8 & 16 \\ 3 & 9 & 27 & 81 \\ 4 & 16 & 64 & 256 \end{array} \right] \left[ \begin{array}{cccc} x_1 \\ x_2 \\ x_3 \\ x_4 \end{array} \right] = \left[ \begin{array}{cccc} 1 \\ 9 \\ 36 \\ 100 \end{array} \right]$

And this yields…

$\left[ \begin{array}{cccc} x_1 \\ x_2 \\ x_3 \\ x_4 \end{array} \right] = \left[ \begin{array}{cccc} 0 \\ 1/4 \\ 1/2 \\ 1/4 \end{array} \right]$

Ah… hmm. Not what I expected at all, really. Nothing about this fits with what I thought I’d find. That zero is especially surprising. That means the number of terms may not increase linearly. For this step, it actually stays at three. So we have:

$\displaystyle\sum_{x=1}^N x^3 = \frac{{N^4} + 2{N^3 }+ {N^2}}{4}$

And for the fourth power… blech. This doesn’t look patterned at all. Here’s the formulas for fourth, fifth, and sixth:

$\displaystyle\sum_{x=1}^N x^4 = \frac{6{N^5} + 15{N^4} + 10{N^3 } - {N}}{30}$

$\displaystyle\sum_{x=1}^N x^5 = \frac{2{N^6} + 6{N^5} + 5{N^4} - {N^2}}{12}$

$\displaystyle\sum_{x=1}^N x^6 = \frac{6{N^7} + 21{N^6} + 21{N^5} -7{N^3} + {N}}{42}$

HOLD THE PHONE. Wait, wait wait wait. Pause. If you were to distribute the denominator, that is, to split this fraction into parts, there is a pattern, albeit complex. I’m seeing some interesting changes in the seemingly random coefficients when I force the denominator to be equal to the power I’m summing.

Here’s a python script that calculates the coefficients from highest to lowest (underscores represent whitespace):

#!/usr/bin/python from numpy import zeros,ones,array,float64,linalg from LUdecomp import * n = 0 TOL = 10e-6 while 1: _ n +=1 _ a = zeros((n,n),dtype=float64) _ b = zeros((n),dtype=float64) _ for i in range(n): _ _ for j in range(n): _ _ _ a[i,j] = (i+1)**(j+1) _ _ if i==0: _ _ _ b[i] = 1 _ _ else: _ _ _ b[i] = b[i-1] + a[i][n-2] _ LU = LUdecomp(a) _ b = LUsolve(LU,b) _ c = b _ for i in range(n): _ _ if abs(c[n-i-1]) < TOL: c[n-i-1] = 0 _ print round(n*c[n-i-1], n/2), "\t", _ print _ try: _ _ raw_input() _ except EOFError: _ _ break

You’re just dying to see the results, aren’t you? I can feel the enthusiasm here.

1 1 1.0 1 1.5 0.50 1 2.0 1.000 0 1 2.5 1.666 0 -0.166 1 3.0 2.500 0 -0.500 0 1 3.5 3.500 0 -1.166 0 0.166 1 4.0 4.666 0 -2.333 0 0.666 0 1 4.5 6.000 0 -4.200 0 2.000 0 -0.30 1 5.0 7.500 0 -7.000 0 5.000 0 -1.50 0 1 5.5 9.166 0 -11.00 0 11.00 0 -5.50 0 0.833 1 6.0 11.00 0 -16.50 0 22.00 0 -16.5 0 5.000 0 1 6.5 13.00 0 -23.83 0 40.86 0 -42.9 0 21.66 0 -3.290 1 7.0 15.16 0 -33.36 0 71.50 0 -100. 0 75.83 0 -23.03 0

There’s definitely a pattern  in there, column by column. For example, our highest power’s coefficient is always one (admittedly, that one is by design). The second column is a linear function. The third is quadratic (it’s one-sixth of the first function in this post). The next column is zeroes. No idea why.

HOLY MOTHER OF LIEBNIZ, I’ve got it. I originally figured there was a bit of rounding error in there, but it was just weird numbers. Those terms along the diagonal were pretty suspicious, though. If you scale each column by a value that makes the diagonal the set of naturals (with non-prime evens zeroed), you get an oddly divided version of Pascal’s triangle!

1 1 2. 1 3. 3. 1 4. 6. 0 1 5. 10 0 5.00 1 6. 15 0 15.0 0 1 7. 21 0 35.0 0 7.00 1 8. 28 0 70.0 0 28.0 0 1 9. 36 0 126. 0 84.0 0 9.00 1 10 45 0 210. 0 210. 0 45.0 0 1 11 55 0 330. 0 462. 0 165. 0 11.0 1 12 66 0 495. 0 924. 0 495. 0 66.0 0 1 13 78 0 715. 0 1716 0 1287 0 286. 0 13 1 14 91 0 1001 0 3003 0 3003 0 1001 0 91 0

So now, I proudly present Dobbs’s Power Summation Rule:

For P>0, the sum of all natural numbers up to N each raised to the P power can be given by:

$\displaystyle\sum_{x=0}^N x^{P-1} = \frac{N^{P-1}}{2} + \displaystyle\sum_{x=0}^{\lfloor (P-1)/2 \rfloor} {P \choose 2x} \frac{N^{P-2x}}{P \times c(x)}$

where c(x) is a rather strange function:

c(0) = 1
c(1) = 6
c(2) = -30
c(3) = 42
c(4) = -30
c(5) = 13.2

1. Mike Farcasin - January 28, 2010

If you have a real formula for c(x) – great. Otherwise, ???

My general rule for math proofs is: If you’ve thought of it, someone else has published it.

2. Mike Farcasin - January 28, 2010

Also, isn’t sum[1,…,n](x) = n*(n+1)/2? And sum[1,…,n](x^3) = (n+1)*(2n+3)/6, and so on?

3. eric22222 - January 28, 2010

1a: I haven’t managed to figure out c yet. I’d like to look at the table of values, see if a pattern develops, but that will involve solving some high-order matrices, which can be prone to error. Regardless, each column is still proportional to each diagonal of Pascal’s triangle. The final formula brings everything together except what value the columns have to be scaled by.

1b: That’s not just a general rule, that’s a theorem.

2a: Yes, that’s the same as the first formula on the page (I probably should label each one…). The only difference is that I factored out n(n+1) to get n^2 + n.

2b:No, that formula you listed doesn’t seem to work. Though (2n+1)(n+1)/6 is the sum of squares, if that’s the factorization you were looking for.

4. M.J. - July 19, 2010

Did you use latex to write this?

5. M.J. - July 19, 2010

2) I’m impressed (with the math not the formating, but the formating is good as well).

3) What made you think to scale the collums like that?

6. M.J. - July 19, 2010

I believe I have a way of solving the problem of the final coeffecients in the formula polynomials being so small that the computer inteprets them as zero.

Solve for the final coeffecients individualy using the determinent method (actual name is some dead guy I don’t remember).

This would still give you the same numerical analysis problem left as is, but the determinent method uses the determinent of a matrix over anther so if you just take the inverse there by flipping the fraction it might give you usable answers for a few more higher order matrices.

– I believe another way of writing your c(x)’s is the inverse of the final coeffecients in the formula polynomials, if you don’t mess with them at all.

7. M.J. - July 19, 2010

Without grammar problems and spelling issues:

I believe I have a way of solving the problem of the final coefficients in the formula polynomials being so small that the computer interprets them as zero.

Solve for the final coefficients individually using the determinant method (actual name is some dead guy I don’t remember).

This would still give you the same numerical analysis problem left as is, but the determinant method uses the determinant of a matrix over anther so if you just take the inverse there by flipping the fraction it might give you usable answers for a few higher order matrices.

– I believe another way of writing your c(x)’s is the inverse of the final coefficients in the formula polynomials, if you don’t mess with them at all.

8. M.J. - July 19, 2010

Tried it and it doesn’t seam to help. It was worse than before probably because the the determinants are such large numbers. Looks like I didn’t tell you anything you didn’t already know.

9. M.J. - July 19, 2010

Tried it and it doesn’t seem to help. It was worse than before probably because the determinants are such large numbers. Looks like I didn’t tell you anything you didn’t already know.

10. Kaleb - July 17, 2011

Your python results are supposed to have the coefficients? These don’t even match the coefficients you solved for above.

I’ve figured out your pattern and why it’s similar to Pascal’s triangle.

When I have time I’ll compose my notes and post them.

11. Kaleb - July 17, 2011

One additional note. You should know there is a problem with your results when you get negative coefficients. Given that you set up the linear matrix equation, I assume you can figure out why that is. It’s completely non-sensical.