art with code

2009-06-13

Sum representation of integer powers

The power xn where x,n ∈ N can be represented as an nth-order sum where the innermost factor is n!.

First, consider x1: the difference between x1 and (x+1)1 is 1. So we have a first-order sum where the innermost factor is 1! (= 1.)

x^1 = sum(i = 0..x, 1)

Now let's look at x2. Let's write the sequence of x2 from -3 to +3 and mark under each two elements the difference between them:

9 4 1 0 1 4 9
-5 -3 -1 1 3 5
2 2 2 2 2

From this we see that we have a second-order sum where the innermost factor is 2! (=2) and the outer factor is -1 (going diagonally left from zero.)

x^2 = -1*sum(i = 0..x, 2*i*sum(j = 0..i, 1))

We can now give a recursive function for the sums that takes a list of factors as its argument (this one only works for positive integers though):

sumMap lst f = sum (map f lst)

sums [] i = 0
sums [x] i = x * i
sums (x:xs) i = x*i + sumMap [0..i] (sums xs)

Then, let's look at the left side of x6:

46656 15625 4096 729 64 1 0 1
-31031 -11529 -3367 -665 -63 -1 1
19502 8162 2702 602 62 2
-11340 -5460 -2100 -540 -60
5880 3360 1560 480
-2520 -1800 -1080
720 720

From which we get the factors [-1, 62, -540, 1560, -1800, 720] and

x^6 = -1*sum(a=0..x, 62*sum(b=0..a, -540*sum(c=0..b, 1560*sum(d=0..c, -1800*sum(e=0..d, 720*sum(f=0..e, 1))))))
or
pow6 = sums [-1, 62, -540, 1560, -1800, 720]

In the general case, the first factor is -1(n-1), the second factor is -2n + 2 * -1n, the second to last factor is -(n-1)n! * 2-1 and the last factor is n!. I don't know about the rest of the factors.

Fun with cubes


Here's the difference grid for the third power:

-27 -8 -1 0 1 8 27
19 7 1 1 7 19
-12 -6 0 6 12
6 6 6 6

Which gives the factors [1, -6, 6].

One result of the sum representation is that each x cubed minus x is divisible by 6: 6 | x3 - x. Or put another way, x3 = x + 6k, k ∈ Z. And the sum between two cubes minus the sum of the bases is also divisible by six: 6 | x3 + y3 - (x + y).

We also see that the difference between any two integer cubes grows as a second order function: n3 - (n-1)3 = 6(n/2)(n+1)+1 = 3n2+3n+1.

cubeDiff n = 3*(n^2 + n) + 1
pow3 n = sumMap [0..n-1] cubeDiff

-- pow3 5
-- 125

There's another amusing difference grid in (x3 - x) / 6:

0 1 4 10 20 35 56 84
1 3 6 10 15 21 28
2 3 4 5 6 7
1 1 1 1 1

No comments:

Blog Archive