{"id":1030,"date":"2018-01-19T11:41:39","date_gmt":"2018-01-19T11:41:39","guid":{"rendered":"http:\/\/mathscitech.org\/articles\/?p=1030"},"modified":"2023-08-28T20:10:04","modified_gmt":"2023-08-28T19:10:04","slug":"finite-summations-3","status":"publish","type":"post","link":"https:\/\/mathscitech.org\/articles\/finite-summations-3","title":{"rendered":"Sum of Integer Powers (Part 3)"},"content":{"rendered":"

(Discrete Mathematics Techniques III)<\/strong><\/p>\n

1st ed. Apr 2nd, 2010<\/em><\/p>\n

Abstract<\/strong>
\nThis is the last in the 3-part series of articles on finding for oneself the solution to the sum of integer power problem, and in the process discovering the Bernoulli numbers. In Part 3 (this paper)<\/strong>, we find a direct<\/strong> closed-form solution, i.e. one that does not<\/strong> 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<\/a> 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<\/a> and Octave\/Matlab codes for directly computing<\/a> the closed-form solutions are included in the Appendices<\/a>.<\/p>\n

A lovely paper by Bearden (March 1996, American Mathematical Monthly)<\/a>, which was shared with me by a reader, tells the mathematical story nicely, with much of the history filled in.<\/p>\n

\n <\/p>\n

\n

NOTE: This paper contains many formulas. As such, you may prefer reading the paper as a typeset PDF<\/a><\/em><\/strong>.<\/p>\n

\n

\n

Finding a Closed-Form solution for S_p(N) = \\sum_{k=1}^N k^p using a Direct Method<\/h3>\n

Motivation<\/h4>\n

\n Our goal is to obtain, without using iteration, a closed form solution for the general case of the finite-summation-of-integer-powers problem:
\n <\/p>\n

\n \\displaystyle S_p(N) = \\sum_{k=1}^N k^p, \\mbox{ (where } p \\in \\mathbb{N} = \\{0,1,2,\\ldots\\}; N\\geq0) \\ \\ \\ \\ \\ (1)<\/p>\n

<\/a> Recall that in Part 2 of this paper<\/a> <\/a>, we used a method of recurrence relations to obtain the following results about S_p(N): <\/p>\n

    \n
  1. S_p(N) may be expressed as a linear recurrence relation that uses the p-1 lower order formulas S_j(N) and S_j(N-1), \\ \\ (j = 1,\\ldots,p-1) as follows:
    \n    <\/p>\n

    \n\\displaystyle S_p(N) = \\frac{1}{1+\\alpha_p}\\left\\{N^2 + N^p + \\sum_{j=1}^{p-1} C_j(N) S_j(N-1) - \\sum_{j=1}^{p-1} \\alpha_j S_j(N) \\right\\}, \\ \\ \\ \\ \\ (2).<\/p>\n

    <\/a>
    \nThe \\alpha_j in (2) are the coefficients from the (p-1)-st polynomial solution S_{p-1}(N), while the terms C_j(N) are defined in terms of binomial coefficients    1<\/a><\/sup> as:<\/p>\n

    \n\\displaystyle C_j(N) = \\left[\\binom{p-1}{j}N - \\binom{p-1}{j-1}\\right].<\/p>\n

  2. The closed form solution of S_p(N) is a polynomial in N of degree p+1 with rational coefficients and a constant term equal to zero.\n<\/ol>\n

    \n While the expression for S_p(N) in (2)<\/a> is indeed accurate, it requires repeated iteration to obtain the closed form expression for any particular p. Such an approach without the assistance of a computer algebra system such as Maxima<\/a>2<\/a><\/sup> would be prohibitively time-consuming and prone to error. <\/p>\n

    We are hence left with the following question: <\/p>\n

    Can we find a closed-form solution for the coefficients of the general solution polynomial that can be obtained directly<\/em>, i.e. that does not require iteration?<\/p><\/blockquote>\n

    This paper uses linear algebra and matrices to achieve precisely this goal.<\/p>\n

    \n

    The Direct Approach<\/h3>\n

    Polynomial with Undetermined Coefficients <\/h4>\n

    Since we have established in (2)<\/a> that S_p(N) is a polynomial of order p+1 with no constant term, we may write down the closed form solution of S_p(N) in the form:
    \n     <\/p>\n

    \n \\displaystyle S_p(N) := \\sum_{j=1}^{p+1} a_j N^j\\ \\ \\ \\ \\ (3)<\/p>\n

    <\/a> where a_j, \\ (j = 1,\\ 2,\\ \\ldots,\\ p+1), are coefficients that have yet to be determined. As a first step towards determining these coefficients, observe that every finite summation can be written as a first order recurrence in N by peeling off the last summand:
    \n    <\/p>\n

    \n\\displaystyle S_p(N+1) = S_p(N) + (N+1)^p.\\ \\ \\ \\ \\ (4)<\/p>\n

    <\/a> Substituting (3)<\/a> into (4)<\/a> gives:
    \n    <\/p>\n

    \n\\displaystyle \\sum_{j=1}^{p+1}a_j (N+1)^j = \\sum_{j=1}^{p+1} a_j N^j + (N+1)^p.\\ \\ \\ \\ \\ (5)<\/p>\n

    <\/a><\/p>\n

    \n

    Summation Manipulations <\/h4>\n

    \n What follows is a sequence of summation manipulations3<\/a><\/sup> and simplifications of (5)<\/a> aimed at obtaining an expression from which a closed-form solution for the coefficicents a_{j} becomes transparent:<\/p>\n