## Wednesday, January 15, 2014

### Sum of Powers

In the sum of powers problem, we are looking for the sum of the pth power of the first n integers. In this post, we consider the problem of determining a polynomial expression in n for a given power. The best known case is for p = 1, namely,
More generally, we should like a formula for a polynomial fp such that
We will begin by defining a function and proceed to prove that it satisfies the above equality. We define:

Proposition 1. For all real numbers n and natural numbers p,
Proof:  First we observe that (n + 1) – n = 1 = (n + 1)0, so that we have our induction base set. Suppose that for any real number n > 0 and a given natural number p we have,

Now, given any real number n > 0,
which completes the argument.■

What remains is an induction argument to show the sum (restricting n to natural numbers), but this is left as an exercise.  The formula we have given for fp allows us to calculate the first p sum of powers polynomials in time O(p2) which is a big improvement when compared to solving a system of linear equations to find the largest of them, which would require time O(p3) (to find all of them using a system of linear equations requires O(p4)).

The following Maxima program and its output, gives a demonstration of how to implement the above formula:

[n,n^2/2+n/2,n^3/3+n^2/2+n/6,n^4/4+n^3/2+n^2/4,n^5/5+n^4/2+n^3/3-n/30,n^6/6+n^5/2+(5*n^4)/12-n^2/12]