Finite Summation of Integer Powers (Part 3)

(Discrete Mathematics Techniques III)

We find a direct closed-form solution, i.e. one that does not require iteration, for the general case of the finite-summation-of-integer-powers problem S_p(N) = \sum_{k=1}^{N} k^p. Having established in Part 2 that the closed-form solution is a polynomial, the summation is here rewritten as the sum of the p+1 independent monomials a_j N^j (1 \leq j \leq p+1), where the a_j are unknown coefficients. Using the recurrence relation S_p(N+1) = S_p(N) + (N+1)^p, we obtain a linear combination of the monomials, which reduces to an easily solvable (p+1)-by-(p+1) triangular linear system in the unknown coefficients a_j of the closed-form polynomial solution. Maxima and Octave/Matlab codes for directly computing the closed-form solutions are included in the Appendices.

Continue reading this article…

Dear Readers!

Our Google+ (Buzz) page is where we publish more regular (~monthly), shorter posts. Feel free to check it out! Full length articles will continue to be published here, with notifications through the Feed (you can join the list below).