(Discrete Mathematics Techniques II)
We solve the general case of the finite-summation-of-integer-powers problem for arbitrary , and obtain a -th order recurrence relation that can be used to iteratively obtain the closed form polynomial for for any given . Source code is given for computing these polynomials using Maxima, an open-source (free) symbolic computation platform. (Note: This article generalizes the recurrence relation approach that is motivated and illustrated for small in Part 1. A direct matrix method for computing the closed form solutions is given in Part 3.)
NOTE: This paper contains many formulas. As such, you may prefer reading the paper as a typeset PDF.
Outline: We obtain a simple first-order recurrence relation (2) and a more complicated recurrence relation (5) that involves the coefficients of a lower order solution to (1). A sequence of manipulations followed by substitution of the first recurrence into the second yields the recurrence relation solution (10). Induction on shows that this is indeed the solution we seek, and that the closed form solution is a polynomial of degree with rational coefficients and no constant term. The recurrence relation (10) allows the closed form expressions to (1) to be computed iteratively for any . A direct (non-iterative) matrix method for computing the closed form solutions is given in Part 3 of this paper.
Deriving the Solution
Proceeding now to the solution:
Claim 1 The solution to (1) is a polynomial of degree with rational coefficients and no constant term.
Proof: (By Induction)
Base case : the solution is immediate: . This is a polynomial of degree 1 with rational coefficients and no constant term.
For the inductive case, suppose the claim to be true for powers . We shall show that it is then true for case .
Obtain the following recurrence directly from the problem statement (1):
This is a first recurrence.
Obtain a second recurrence from the problem statement (1) as follows: we have supposed in our induction hypothesis that the closed form solutions for the lower order problems are polynomials of a certain form. So we may write the solution as:
In writing (3), the highest order term, , and its coefficient , are emphasized.
Change variables in (3) from to , and solve for the highest order term :
Considering each summation in (5) separately:
First summation in (5)…
Expand the first summation and gather the terms by like ()-powers of :
Expand the binomial power in (6) using the binomial formula:
Interchange the order of summation:
Pull the term out of both summations. NOTE: 1
Recognize the appearance of the finite sum of integer powers, but of lower order:
Shifting indices in second summation, see [GKP] and [Knu]for index manipulation techniques:
Peel off -th term from first sum and -th term from second sum to combine the rest:
Second summation in (5)…
The second summation term in (5) is a double summation. Recognize that the finite sum of summed over is in fact . So interchange the order of summation and proceed:
Arriving at the final form of the second recurrence…
is a linear polynomial in with binomial coefficients.
where the are the coefficients from the closed form solution of , and
Inspection shows that the general solution (10) is a polynomial in that satisfies all three elements of Claim 1:
- it has degree : is a -th order polynomial multiplied by the linear polynomial ,
- it has no constant term
- it has rational coefficients: the coefficients are sums and products of coefficients of lower order solutions (which are rational by the inductive hypothesis) and binomial coefficients (positive integers).
The Claim is therefore shown by induction.
Remarks We have in (10) a recurrence formula for the finite-summation-of-integer-powers problem that can be used to derive closed form expressions for any given .
Listing of Closed Form Solutions
Figure 1 shows the first 10 closed form expressions computed iteratively using Maxima. Maxima source code is provided in Appendix A.
Summary We have developed a -th order recurrence relation (10) that, when used iteratively, gives the general closed form formula for the finite summation for any given .
Computing closed form formulas for specific from this -th order recurrence is made substantially easier by a computer package, whether this is a symbolical algebra package such as Maxima, that gets through the tangle of algebra that arises out of what is effectively a chain of substitutions, or a programming language such as Ruby, that has flexible language structures allowing an iteration such as this to be coded up easily.
Appendix A provides Maxima source code that uses (10) to iteratively compute the closed form expression for for any given .
Next Steps Can we do better? Specifically, can we find a closed form expression for solution that can be obtained directly, i.e. without requiring iteration? What relations hold between and among the ? These matters are taken up in Part 3 of this paper [EO10]. In particular, Part 3 uses matrix methods to obtain the closed form expressions shown in Figure 1 directly and without requiring iteration, by solving a linear system.
Appendix A: Maxima Source Code for Computing
This Appendix gives Maxima source code for computing closed form expressions for the finite-summation-of-integer-powers problem (1) using the -th order recurrence relation (10). Appendix B shows how both Maxima and Ruby can be used for cross-checking both the derivation and the correctness of the implementation.
The following Maxima code iteratively computes solutions for given values of p, using this $p$-th order recurrence relation.
Excerpt (Full Source):
CORE COMPUTATION: p-th ORDER RECURRENCE
PRIVATE Function: Computes p-th solution using p-th order recurrence relation
of Equation (1-SOL), and prior solutions.
Solution in: “Finite Summation of Integer Powers, Part 2”, Assad Ebrahim, Jan 2010
Paper at: http://mathscitech.org/papers/ebrahim-sum-powers-2.pdf */
/* initial value */
get_next_SpN(p) := block([a,sum1,sum2],
s(n) := n,
c(p,j,n) := n*binomial(p-1,j) - binomial(p-1,j-1),/* definition */
a[p-1] : getcoeffs(s,p-1),/* get prior solution’s coefficients */
/* compute the two summations in Equation (1-SOL) */
sum1 : ratsimp(sum(c(p,k,n)*s[k](n-1),k,1,p-1)),
sum2 : ratsimp(sum(a[p-1][k+1]*s[k](n),k,1,p-1)),
/* compute and assign solution (1-SOL) */
define(s[p](n),ratsimp((1/(1+a[p-1][p+1]))*(n^2 + n^p + sum1 - sum2)))
Appendix B: Using computing software to compute and check the derivation (10)
Cross-Checking Derivation of the General Formula Using Maxima and Ruby
We can check the derivation using computing software, as follows:
- Use Maxima to obtain the simplified formula for . (Figure 2)
Now, you could determine the by hand, e.g.
but why bother? Maxima has the facility to evaluate binomial coefficients, so just code up the general definition:
c(p,j,n):=n*binom(p-1,j) – binom(p-1,j-1);
- Use Maxima to evaluate this at, say, (Figure 3)
- Use Ruby to perform the brute force summation (Figure 4). This yields the same value: 220,825.
Observe that the two computations of match. One can check at various values of and convince oneself that the derivation is correct. Note: Being convinced of the correctness of a derivation through computing values is not the same thing as a proof of correctness. It is, however, important to catch errors, both typographical and in implementation.
Appendix C: Why
A key step in the derivation of (7) from (6) relies on the fact that . Recall, we peeled off the term of the inner summation to get: . Peeling this out of the outer summation requires considering the expression for all . Now, 0 raised to any positive power is 0, so we can dispel the case of . But what is ? A decision must be made: it is either or . Indeterminacy is not an options, since the situation is real and is required to continue the simplification.
This question is treated here: Why
I thank Carol Ouellette for reading an early draft of this paper and for many thoughtful comments and suggestions.
>> Continue reading: Finite Summations of Integer Powers , Part 3
This article is available for download as a PDF here.
The Maxima source code implementing the recurrence relation solution is available for download here.
Finite summation of integer powers xp, part 1.
Finite summation of integer powers xp, part 3.
Assad Ebrahim and Carol Ouellette.
Concrete Mathematics: A Foundation for Computer Science.
Ron Graham, Donald Knuth, and Oren Patashnik.
1994, 2nd edition.
The Art of Computer Programming (3 Volumes).
1968, 1969, 1973 (Latest boxed edition of 2011 includes Vol4A)
- Peel off the term of the inner summation to get: . Peeling this out of the outer summation requires considering the value of the expression when summed over all values of . Now, 0 raised to any positive power is 0, so we can dispel the case . This leaves:
What is ? A decision must be made: it is either or . Indeterminacy is not an option, since the situation is real and is required to continue the simplification. This step in the derivation of (7) from (6) relies on the empirical fact that .
Definition 1 (Empirical) for , where are discrete variables.