{"id":622,"date":"2018-01-20T19:57:14","date_gmt":"2018-01-20T19:57:14","guid":{"rendered":"http:\/\/mathscitech.org\/articles\/?p=622"},"modified":"2024-05-10T13:19:10","modified_gmt":"2024-05-10T12:19:10","slug":"finite-summations-2","status":"publish","type":"post","link":"https:\/\/mathscitech.org\/articles\/finite-summations-2","title":{"rendered":"Sum of Integer Powers (Part 2)"},"content":{"rendered":"

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

1st ed. Feb 8th, 2010<\/em><\/p>\n

Abstract<\/strong>
\nWe continue the 3-part paper exploring how one might solve for themselves the general case of the sum-of-integer-powers problem S_p(N) = \\sum_{k=1}^{N} k^p for arbitrary p, the coefficients of whose solution are the famous Bernoulli numbers (1716). In this paper we show to how obtain a p-th order recurrence relation that can be used to iteratively<\/strong> obtain the closed form polynomial for S_p(N) for any given p. Source code is given for computing these polynomials using Maxima<\/a>, an open-source (free) symbolic computation platform. <\/p>\n

This article generalizes the recurrence relation approach that is motivated and illustrated for small p in Part 1<\/em><\/a>. A direct<\/strong> (non-recursive) method for computing the closed-form solutions is given in Part 3<\/em><\/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

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

\n

Finding S_p(N) = \\sum_{k=1}^N k^p<\/h3>\n

We desire a general formula that solves the finite-summation-of-integer-powers problem for any positive integer power p: <\/a><\/p>\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

We proceed using the method of recurrence relations that was illustrated for small p in Part 1 of this paper<\/a> [Ebr10]<\/a> and that we prove inductively here.<\/p>\n

\nOutline:<\/b> We obtain a simple first-order recurrence relation (2)<\/a> and a more complicated recurrence relation (5)<\/a> that involves the coefficients of a lower order solution to (1)<\/a>. A sequence of manipulations followed by substitution of the first recurrence into the second yields the recurrence relation solution (10)<\/a>. Induction on p shows that this is indeed the solution we seek, and that the closed form solution is a polynomial of degree p+1 with rational coefficients and no constant term. The recurrence relation (10)<\/a> allows the closed form expressions<\/a> to (1)<\/a> to be computed iteratively for any p. A direct (non-iterative) matrix method for computing the closed form solutions is given in Part 3<\/em><\/a> of this paper.<\/p>\n

Deriving the Solution<\/h4>\n

\nProceeding now to the solution:<\/p>\n

Claim 1<\/b> The solution to (1)<\/a> is a polynomial of degree p+1 with rational coefficients and no constant term. <\/em><\/p><\/blockquote>\n

In particular we shall find an expression (10)<\/a> for this polynomial that allows a closed form for (1)<\/a> to be computed iteratively for any given p and all N.<\/p>\n

\nProof: <\/b> (By Induction)
\nBase case p=0: the solution is immediate: S_0(N) = \\sum_{k=1}^N 1 = N. This is a polynomial of degree 1 with rational coefficients and no constant term.<\/p>\n

\nFor the inductive case, suppose the claim to be true for powers 1,2,\\ldots,p-1. We shall show that it is then true for case p.<\/p>\n

\nObtain the following recurrence directly from the problem statement (1)<\/a>: <\/a><\/p>\n

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

This is a first recurrence.<\/p>\n

\nObtain a second recurrence from the problem statement (1)<\/a> 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 p-1 solution as: <\/a><\/p>\n

\\displaystyle S_{p-1}(N) = \\alpha_p N^p + \\sum_{j=1}^{p-1} \\alpha_j N^j.\\ \\ \\ \\ (p\\geq1; N\\geq0) \\ \\ \\ \\ \\ (3)<\/p>\n

In writing (3)<\/a>, the highest order term, N^p, and its coefficient \\alpha_p, are emphasized. <\/p>\n

\nChange variables in (3)<\/a> from N to K, and solve for the highest order term K^p: <\/a><\/p>\n

\\displaystyle K^p = \\frac{1}{\\alpha_p}\\left[S_{p-1}(K) - \\sum_{j=1}^{p-1} \\alpha_j K^j \\right].\\ \\ \\ \\ \\ (4)<\/p>\n

\nSubstituting (4)<\/a> into (1)<\/a> gives the desired second recurrence, which we break into two summations for separate treatment:
\n<\/a> <\/p>\n

\\displaystyle S_p(N) = \\sum_{K=1}^N \\frac{1}{\\alpha_p} \\left[S_{p-1}(K) - \\sum_{j=1}^{p-1} \\alpha_j K^j \\right]
\n\\displaystyle = \\frac{1}{\\alpha_p} \\sum_{K=1}^N S_{p-1}(K) - \\frac{1}{\\alpha_p} \\sum_{K=1}^N \\sum_{j=1}^{p-1} \\alpha_j K^j.\\ \\ \\ \\ \\ (5) <\/p>\n

Considering each summation in (5)<\/a> separately:<\/p>\n

First summation in (5)<\/a>…<\/h4>\n

Expand the first summation and gather the terms by like ({p-1})-powers of K: <\/p>\n

\\displaystyle \\sum_{k=1}^N S_{p-1}(K) = S_{p-1}(1) + S_{p-1}(2) + S_{p-1}(3) + \\ldots + S_{p-1}(N)
\n \\displaystyle \\ \\ \\ \\ \\ = 1^{p-1} + (1^{p-1} + 2^{p-1}) + (1^{p-1} + 2^{p-1} + 3^{p-1}) + \\ldots + (1^{p-1} + 2^{p-1} + 3^{p-1} + \\ldots + N^{p-1})
\n \\displaystyle \\ \\ \\ \\ \\ = N(1^{p-1}) + (N-1)(2^{p-1}) + \\ldots + 2(N-1)^{p-1} + 1(N^{p-1})
\n \\displaystyle \\ \\ \\ \\ \\ = \\sum_{k=0}^{N-1} (N-K)(K+1)^{p-1}\\ \\ \\ \\ \\ (6)<\/a>
\n Expand the binomial power in (6)<\/a> using the binomial formula:
\n \\displaystyle \\ \\ \\ \\ \\ = \\sum_{k=0}^{N-1} (N-K)\\sum_{j=0}^{p-1} \\binom{p-1}{j} K^j
\n \\displaystyle \\ \\ \\ \\ \\ = \\sum_{k=0}^{N-1} \\sum_{j=0}^{p-1} (N-K)\\binom{p-1}{j} K^j
\n \\displaystyle \\ \\ \\ \\ \\ = \\sum_{k=0}^{N-1} \\sum_{j=0}^{p-1} \\binom{p-1}{j} \\left[NK^j -K^{j+1}\\right]
\n Interchange the order of summation:
\n \\displaystyle \\ \\ \\ \\ \\ = \\sum_{j=0}^{p-1} \\binom{p-1}{j} \\sum_{k=0}^{N-1} \\left[NK^j -K^{j+1}\\right]
\n Pull the K=0 term out of both summations. NOTE: 0^0 = 1 1<\/a><\/sup>
\n\\displaystyle \\ \\ \\ \\ \\ = N + \\sum_{j=0}^{p-1} \\binom{p-1}{j} \\sum_{k=1}^{N-1} \\left[NK^j -K^{j+1}\\right]
\n\\displaystyle \\ \\ \\ \\ \\ = N + \\sum_{j=0}^{p-1} \\binom{p-1}{j} \\left[\\sum_{k=1}^{N-1} NK^j -\\sum_{k=1}^{N-1}K^{j+1}\\right]
\nRecognize the appearance of the finite sum of integer powers, but of lower order:
\n\\displaystyle \\ \\ \\ \\ \\ = N + \\sum_{j=0}^{p-1} \\binom{p-1}{j} NS_j(N-1) - \\sum_{j=0}^{p-1} \\binom{p-1}{j} S_{j+1}(N-1)
\nShifting indices in second summation, see [GKP]<\/a> and [Knu]<\/a>for index manipulation techniques:
\n\\displaystyle \\ \\ \\ \\ \\ = N + \\sum_{j=0}^{p-1} \\binom{p-1}{j} N S_j(N-1) - \\sum_{j=1}^{p} \\binom{p-1}{j-1} S_j(N-1)
\nPeel off 0-th term from first sum and p-th term from second sum to combine the rest:
\n\\displaystyle \\ \\ \\ \\ \\ = N + N(N-1) - S_p(N-1) + \\sum_{j=1}^{p-1} S_j(N-1)\\left[N\\binom{p-1}{j} - \\binom{p-1}{j-1}\\right]
\n\\displaystyle \\ \\ \\ \\ \\ = N^2 - S_p(N-1) + \\sum_{j=1}^{p-1} S_j(N-1)\\left[N\\binom{p-1}{j} - \\binom{p-1}{j-1}\\right]\\ \\ \\ \\ (7)<\/a>\n<\/p>\n

Second summation in (5)<\/a>…<\/h4>\n

The second summation term in (5)<\/a> is a double summation. Recognize that the finite sum of K^j summed over K is in fact S_j(N). So interchange the order of summation and proceed: <\/p>\n

\\sum_{k=1}^N \\sum_{j=1}^{p-1} \\alpha_j K^j = \\sum_{j=1}^{p-1} \\alpha_j \\left(\\sum_{k=1}^N k^j\\right)
\n\\displaystyle \\ \\ \\ \\ \\ = \\sum_{j=1}^{p-1} \\alpha_j S_j(N).\\ \\ \\ \\ (8)<\/a><\/p>\n

Arriving at the final form of the second recurrence…<\/h4>\n

Combining (7)<\/a> and (8)<\/a> into the second recurrence (5)<\/a> gives the simplified second recurrence: <\/a><\/p>\n

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

where <\/p>\n

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

is a linear polynomial in N with binomial coefficients.<\/p>\n

\nSubstituting S_p(N-1) from the first recurrence (2)<\/a> into (5)<\/a> yields: <\/p>\n

\\displaystyle S_p(N) = \\frac{1}{\\alpha_p} \\left\\{N^2 - S_p(N) + 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\\}.<\/p>\n

Collecting the S_p(N) terms and simplifying gives a p-th order recurrence relation that supplies a closed form expression for S_p(N) in terms of lower order summations: <\/a><\/p>\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\\}, \\ \\ \\ \\ \\ (10)<\/p>\n

where the \\alpha_j are the coefficients from the closed form solution of S_{p-1}(N), and <\/p>\n

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

\nInspection shows that the general solution (10)<\/a> is a polynomial in N that satisfies all three elements of Claim 1: <\/p>\n

    \n
  1. it has degree p+1: S_{p-1}(N-1) is a p-th order polynomial multiplied by the linear polynomial C_p-1(N),\n
  2. it has no constant term\n
  3. 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).\n<\/ol>\n

    The Claim is therefore shown by induction.<\/p>\n

    \nRemarks<\/b> We have in (10)<\/a> a recurrence formula for the finite-summation-of-integer-powers problem that can be used to derive closed form expressions for any given p. <\/p>\n

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

    Listing of Closed Form Solutions<\/h4>\n

    Figure 1<\/a> shows the first 10 closed form expressions computed iteratively using Maxima. Maxima source code is provided in Appendix A.<\/p>\n

    \n<\/a>Figure 1.<\/strong>
    \n

    \"Figure<\/a>

    Figure 1. Closed form expressions for S_p(N), for p=1,2,...,10, computed using computer algebra system Maxima.<\/p><\/div><\/p>\n

    Conclusion <\/h4>\n

    \nSummary<\/b> We have developed a p-th order recurrence relation (10)<\/a> that, when used iteratively, gives the general closed form formula for the finite summation \\sum_{k=1}^N k^p for any given p. <\/p>\n

    \nComputing closed form formulas for specific p from this p-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.<\/p>\n

    \nAppendix A provides Maxima source code that uses (10)<\/a> to iteratively compute the closed form expression for S_p(N) for any given p.<\/p>\n

    \nNext Steps<\/b> 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 S_p(N)? These matters are taken up in Part 3 of this paper<\/a> [EO10]<\/a>. In particular, Part 3<\/a> uses matrix methods to obtain the closed form expressions shown in Figure 1<\/a> directly and without requiring iteration, by solving a linear system.<\/p>\n

    Appendix A: Maxima Source Code for Computing S_p(N) := \\sum_{k=1}^N k^p <\/h4>\n

    This Appendix gives Maxima source code for computing closed form expressions for the finite-summation-of-integer-powers problem (1)<\/a> using the p-th order recurrence relation (10)<\/a>. Appendix B shows how both Maxima and Ruby can be used for cross-checking both the derivation and the correctness of the implementation.<\/p>\n

    The following Maxima code iteratively computes solutions<\/a> for given values of p, using this $p$-th order recurrence relation.<\/p>\n

    Excerpt<\/strong> (Full Source<\/a>):<\/p>\n

    \n\/* **********************
    \n CORE COMPUTATION: p-th ORDER RECURRENCE
    \n —————————————
    \n PRIVATE Function: Computes p-th solution using p-th order recurrence relation
    \n of Equation (1-SOL), and prior solutions.
    \n Solution in: “Finite Summation of Integer Powers, Part 2”, Assad Ebrahim, Jan 2010
    \n Paper at: http:\/\/mathscitech.org\/papers\/ebrahim-sum-powers-2.pdf *\/
    \n
    \nget_next_SpN(p) := block([a,sum1,sum2],
    \n s[0](n) := n,<\/code> \/* initial value *\/
    \n c(p,j,n) := n*binomial(p-1,j) - binomial(p-1,j-1), <\/code> \/* definition *\/<\/p>\n

    a[p-1] : getcoeffs(s,p-1), <\/code> \/* get prior solution’s coefficients *\/<\/p>\n

    \/* compute the two summations in Equation (1-SOL) *\/
    \n sum1 : ratsimp(sum(c(p,k,n)*s[k](n-1),k,1,p-1)),
    \n sum2 : ratsimp(sum(a[p-1][k+1]*s[k](n),k,1,p-1)),
    \n <\/code>
    \n \/* compute and assign solution (1-SOL) *\/
    \n define(s[p](n),ratsimp((1\/(1+a[p-1][p+1]))*(n^2 + n^p + sum1 - sum2)))
    \n)$
    \n<\/code>\n<\/p><\/blockquote>\n

    \nDownload full Source Code here<\/a> (or grab this file<\/a>).<\/p>\n

    Appendix B: Using computing software to compute and check the derivation (10)<\/a><\/h4>\n

    Cross-Checking Derivation of the General Formula Using Maxima and Ruby<\/b><\/p>\n

    \nWe can check the derivation using computing software, as follows: <\/p>\n