Welcome to Gaia! ::

I had this idea whilest I was out walking... I bet it's a well-known technique but I still think it's pretty neat:

How to derive formulas for sum_0^n q(n) where q(n) is a polynomial that represents the pth term in a sequence...
example:
sum_0^n x^2 = (2n+1)(n)(n+1)/6

Conventions:
Let p(x) always represent a polynomial of degree n
Theorems
1) The degree of p(x+a) - p(x) is n-1
Proof:
Let p(x) = sum_0^n a_i x^i
Clearly the the coefficients of the higest order term of p(x+a) and p(x) are identical and so the degree of p(x+a) - p(x) is less than n
The coefficient of the second highest term in p(x+a) has two contributors:
a_n(x+c)^n and a_{n-1}(x+c)^n-1
The contribution from (x+c)^n is cn a_n and the other term contributes a_{n-1}
in p(x+a) - p(x) the coefficient for the {n-1} term is then c*n*a_n

2) If c=1, then the leading coefficient in p(x+1) - p(x) is the leading coefficient in p'(x).
proof: see above

3) If the nth term in a sequence is represented by the polynomial q(n)... and p(n) IS a polynomial that represents the nth partial sum of sum_0^{infty}, then p(n+1) - p(n) = q(n+1).
Notice:
A) This doesn't prove existance
B) If there IS a p(n), then p(n+1) - p(n) is a polynomial that agrees with q(n+1) for infinitely many values and hence they are equal polynomials
C) the degree of p is 1 more than the degree of q

4) So we now have p(x+1) - p(x) = q(x+1)... If p(x) exists in the first place..... also, for simplicity assume that p(0) = 0 (which isn't as restrictive as it might sound since we can always reindex)

Using these theorems (examples):
Suppose we want a closed form solution for sum_1^n i^2
Here's few terms:
n sum
0 0
1 1
2 5
3 14
4 30
5 55

Now... let's assume there is a closed form solution *and* that it's a polynomial. Let's call it p(x).
From the discussion above we know that
(*) p(x+1)-p(x) = (x+1)^2
From that same discussion we know that the degree of p is 3
We also know p(0) = 0 which implies no constant term... hence:
p(x) = ax^3 + bx^2 + cx
Take the derivative of both sides of (*) twice:
(**) p''(x+1) - p''(x) = 2

Now p''(x) = 6ax + b
so p''(1) - p''(0) = 6a
BUT... by putting x=0 in (**) we get p''(1) - p''(0) = 2
Hence 6a=2 => a=1/3

So we know this:
p(x) = 1/3 x^3 + b x^2 + cx
Now consider the first derivative of p(x):
p'(x) = x^2 + 2bx + c
From this we see that p'(1) - p'(0) = 1+2b
Now we take the first derivative of both sides of (*)
(***) p'(x+1) - p'(x) = 2(x+1)
and by replace x with 0 we get:
p'(1) - p'(0) = 2
Hence 1+2b = 2 => b = 1/2

We're almost there now....
p(x) = 1/3 x^3 + 1/2 x^2 + cx
notice that p(1)-p(0) = 1/3 + 1/2 + c
But we also know that this is (x+1)^2 = 1
Solving for c we get c=1/6

p(x) = 1/3 x^3 + 1/2 x^2 + 1/6 x
OR....
(2x^3 + 3x^2 + x)/6
Factoring out the x:
x(2x^2 + 3x + 1)/6
And then factoring the quadratic by sight:
x(2x+1)(x+1)/6
Voila!

Plugging a few numbers in... we see that it does in fact agree (we could verify by induction too if we were so inclined).

Now... as long as the procedure works for all monomials with coefficient 1 then the usual summation laws allow a closed formula to be calculated for all polynomial q(x)....

HOWEVER... I don't yet have an existance proof proving that
sum_1^n i^m
has a polynomial closed form for all m (although I believe it to be true)

That's not the problem-- that a polynomial expression can be derived for each value of m is certain, however, there is nothing in the procedure to prove that the resulting polynomial expression IS the closed form. The procedure requires a priori:
1) there is a closed form solution
2) the closed form solution is polynomial

As expected, the general solution already exists... it's called Faulhaber's formula (http://en.wikipedia.org/wiki/Faulhaber's_formula) and it involves Bernoulli numbers (http://en.wikipedia.org/wiki/Bernoulli_number), which I found to be unexpected and rather pleasing....