^{th}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

*f*such that

_{p}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

*f*allows us to calculate the first p sum of powers polynomials in time O(p

_{p}^{2}) 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(p

^{3}) (to find all of them using a system of linear equations requires O(p

^{4})).

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]`

## No comments:

Post a Comment