Monday, January 6, 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.■

Proposition 2. For all natural numbers \(n\) and \(p\)
$$f_p(n) = \sum_{i=1}^n{i^p}$$

Proof: First we see from the definition both that \(f_0(1) = 1\) and, for any \(p > 1\)
$$f_{p}(1) = p \Big(\int_0^1 f_{p-1}(x) \mathrm{d}x - 1 \int_0^1 f_{p-1}(x) \mathrm{d}x\Big) + 1 = 1,$$
which establishes \(1 \in S\). Suppose that \(n \in S\). Then
$$f_p(n) = \sum_{i=1}^n{i^p},$$
and from proposition 1
$$f_p(n+1) - f_p(n) = (n + 1)^p$$
which rearranges to
$$f_p(n+1) = f_p(n) + (n+1)^p$$
$$= \sum_{i=1}^n{i^p} + (n+1)^p  = \sum_{i=1}^{n+1}{i^p}$$

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]

No comments: