{"id":585,"date":"2018-01-21T08:50:47","date_gmt":"2018-01-21T08:50:47","guid":{"rendered":"http:\/\/mathscitech.org\/articles\/?p=585"},"modified":"2024-05-10T13:19:00","modified_gmt":"2024-05-10T12:19:00","slug":"finite-summations-1","status":"publish","type":"post","link":"https:\/\/mathscitech.org\/articles\/finite-summations-1","title":{"rendered":"Sum of Integer Powers (Part 1)"},"content":{"rendered":"

2nd ed. January 21, 2018; 1st ed. Feb 8th, 2010<\/em><\/p>\n

Abstract<\/strong>
\nThis three part paper explores solving the sum of powers problem S_r(n) = \\sum_{k=1}^{n} k^r using discrete maths techniques (recurrence relations, matrix systems) to obtain a solution polynomials whose coefficients turn out to be exactly the Bernoulli numbers B_n.
\nPart 1 (this paper)<\/strong> solves the problem using recurrence relations in a way which a high school student could emulate for small r. In Part 2<\/a>, we develop a general recursive solution that works for arbitrary r, from which we can build a table of values to assist in finding the coefficients of the solution polynomial, coefficients that are precisely the Bernoulli numbers<\/a> discovered in 1713. In Part 3<\/a>, we show how by transforming the problem into a linear system, we may obtain a direct (non-recursive) solution which directly calculates the Bernoulli number for any power r. Source code is provided for all solutions. <\/p>\n

Readers who are interested in this topic are referred also to lovely paper by Bearden<\/a> (March 1996, American Mathematical Monthly), which tells the mathematical story and fills in the history (thanks to a reader for this great reference).
\n<\/p>\n

\n

1. Introduction<\/h3>\n

We are looking to find closed form solutions in n for sums-of-powers problems:
\n<\/a><\/p>\n

\\displaystyle S_1(n) = \\sum_{k=1}^{n} k = 1 + 2 + 3 + \\ldots + (n-1) + n\\ \\ \\ \\ \\ \\mbox{(linear)}<\/p>\n

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

 <\/p>\n

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

\\displaystyle S_2(n) = \\sum_{k=1}^{n} k^2 = 1^2 + 2^2 + 3^2 + \\ldots + (n-1)^2 + n^2\\ \\ \\ \\ \\ \\mbox{(squares)}<\/p>\n

\\displaystyle S_3(n) = \\sum_{k=1}^{n} k^3\\ \\ \\ \\ \\ \\mbox{(cubes)}<\/p>\n

\\displaystyle S_4(n) = \\sum_{k=1}^{n} k^4\\ \\ \\ \\ \\ \\mbox{(quarts)}<\/p>\n

and, generally:<\/p>\n

\\displaystyle S_r(n) = \\sum_{k=1}^{n} k^r = 1^r + 2^r + 3^r + \\ldots + (n-1)^r + n^r\\ \\ \\ \\ \\ \\mbox{(r-th powers)}<\/p>\n

2. Solving Linear Sums<\/h3>\n

Consider the linear sum
\n<\/a><\/p>\n

\\displaystyle S_1(n) = \\sum_{k=1}^{n} k = 1 + 2 + 3 + \\ldots + (n-1) + n\\ \\ \\ \\ \\ (1)<\/p>\n

Method 1: Algebraic Insight<\/h4>\n

Tradition1<\/a><\/sup> has it that seven-year-old Gauss solved (1)<\/a> by writing out the sum twice, first forwards then in reverse, and then adding the terms column-wise:<\/p>\n

<\/a>\\displaystyle S_1(n) = 1 + 2 + 3 + \\ldots + (n-2) + (n-1) + n<\/p>\n

<\/a>\\displaystyle S_1(n) = n + (n-1) + (n-2) + \\ldots + 3 + 2 + 1.<\/p>\n

The left hand terms add to 2S_1(n), or twice the original. Each of the right-hand terms adds to n+1 and there are exactly n terms, giving the solution:<\/p>\n

\\displaystyle 2S_1(n) = n(n+1) \\implies S_1(n) = \\tfrac{1}{2}n(n+1) = \\tfrac{1}{2}[n^2 + n] \\ \\ \\ \\ \\ (2).<\/p>\n

Elegant. The key insight here was cleverly rearranging a copy of the sum so that the solution became obvious when added to itself. Is there another way?<\/p>\n

Method 2: Geometric Insight<\/h4>\n

Write down the first few examples of (1)<\/a>:<\/p>\n

\\displaystyle n: 1,2,3,4,5,6,\\ldots<\/p>\n

\\displaystyle S_1(n): 1,3,6,10,15,21,\\ldots<\/p>\n

<\/a>
\n

\"S_1(n)<\/a>

S_1(n) is the blue triangle<\/p><\/div><\/p>\n

Arranging each term \\{1,2,3,4,\\ldots\\} as a row of dots forms a right triangle (Figure 1<\/a>, blue dots) with side lengths and a diagonal each of n dots. S_1(n) is the total number of dots in the triangle, hence the name triangular numbers<\/strong> for S_1(n).<\/p>\n

Finding the desired sum S_1(n), the blue triangle, is now a geometric question, and there are several solutions.<\/p>\n

Solution 2A<\/strong> The blue triangle S_1(n) is found by taking the square of n^2 dots, and removing the diagonal (n dots), which leaves two (red) triangles of side length n-1, S_1(n-1), each having half the remaining dots, or
\n\\displaystyle S_1(n-1) = \\tfrac{1}{2}(n^2 - n) = \\tfrac{1}{2}(n-1)(n).<\/p>\n

We can now shift indices to get the solution as before:
\n\\displaystyle S_1(n) = \\tfrac{1}{2}(n)(n+1).<\/p>\n

Note that this geometric deconstruction also yields recurrence that will be fundamental:
\n\\displaystyle S_1(n) = S_1(n-1) + n \\ \\ \\ \\ \\ (3),
\nwhich says the blue triangle S_1(n) is the red triangle S_1(n-1) with the diagonal n added on.<\/p>\n

Good. Here the insight was using of geometry to represent the sum.<\/p>\n

We now show a third method which motivates the one we will use to find the general solution.<\/p>\n

Method 3: Two Recurrence Relations<\/h4>\n

The definition (1)<\/a> gives a first-order recurrence relation:
\n<\/a><\/p>\n

\\displaystyle S_1(n) = S_1(n-1) + n\\ \\ \\ \\ \\ \\mbox{(5)}<\/p>\n

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

 <\/p>\n

<\/a>
\nThis says that you get from one sum to the next case by adding the next term.
\nIf we had another recurrence, we could solve by substitution or elimination, treating the pair as a system of two equations in two unknowns S_1(n) \\mbox{ and } S_1(n-1).<\/p>\n

The geometric insight above (see Figure 1<\/a>) can be adapted to yield a second recurrence:
\n<\/a><\/p>\n

\\displaystyle S_1(n) = n^2 - S_1(n-1)\\ \\ \\ \\ \\ \\mbox{(6)}<\/p>\n

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

 <\/p>\n

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

This says that the blue triangle S_1(n) remains after removing a smaller copy, the red triangle, S_1(n-1) from the square of n^2 dots.2<\/a><\/sup><\/p>\n

Note that the recurrence (6) can be established by mathematical induction without reference to the geometric thinking that inspired it, which is a desirable simplification.<\/p>\n

With the two recurrences (5) and (6), we can solve by substitution or in this case by directly adding them to get:<\/p>\n

\\displaystyle 2S_1(n) = n^2 + n \\ \\implies \\ S_1(n) = \\frac{1}{2}n(n+1),<\/p>\n

which is the same solution as equation 4 above.<\/p>\n

Remarks<\/strong> Let’s consider what we have just seen.<\/p>\n

The first solution method required the observation that pairs of entries marching in from opposite sides have a constant sum. Rewriting the series twice is a clever way of dealing with the otherwise sticky detail of whether all the entries can be paired, which would depend on whether there are an even or odd number of terms in the sum.<\/p>\n

The second solution required coming upon the suggestive geometric arrangement of dots, from which known results about geometric figures could be used to deduce the closed form formula.<\/p>\n

The third solution has the promise of a general method if we can always find a second recurrence relation. For S_1(n), the geometric arrangement of method 2 suggested the second recurrence, after which obtaining the solution was mechanical.<\/p>\n

We will now solve the problem for every member of the family S_r(n) by prescribing an automatic way of generating the second recurrence using a generalization of the geometric insight of solution 2.<\/p>\n

3. Sum of Squares<\/h3>\n

Consider the sum of squares <\/a><\/p>\n

\\displaystyle S_2(n) = \\sum_1^n k^2\\ \\ \\ \\ \\ (7)<\/p>\n

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

 <\/p>\n

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

The sequence for S_2(n) goes as:<\/p>\n

\\displaystyle n: 1,2,3,4,5,6\\ldots<\/p>\n

\\displaystyle S_2(n): 1,5,14,30,55,91,\\ldots<\/p>\n

Method 1 doesn’t work for S_2(n): matched pairs from opposite ends of the finite sum don’t have a constant sum (92, 60, 44 for S_2(6)).<\/p>\n

Playing with dot arrangements yields a pattern: each square number k^2 is built up as a sum of the first k odd numbers — see Figure 2. 3<\/a><\/sup> We shall exploit this lemma (sum-of-odd-integers-is-square) to obtain the required second recurrence and solve the problem.4<\/a><\/sup><\/p>\n

\"Sum

Figure 2. Sum of Odd Integers<\/p><\/div>\n

Method 3: Two Recurrence Relations<\/h4>\n

The first recurrence relation is immediate from the definition (2)<\/a>: <\/a><\/p>\n

\\displaystyle S_2(n) = S_2(n-1) + n^2.\\ \\ \\ \\ \\ \\mbox{(8)}<\/p>\n

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

For the second recurrence relation write out the definition of S_2(n) and replace each k^2 term using the Sum-of-Odd-Integers-is-Square Lemma (e.g. n^2 = 1 + 3 + 5 + \\ldots + 2n-1). This gives:<\/p>\n

\\displaystyle S_2(n) = 1^2 + 2^2 + 3^2 + \\ldots + n^2
\n\\displaystyle \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ = (1) + (1+3) + (1+3+5) + \\ldots + (1+3+5+\\ldots+(2n-1))\\ \\ \\ \\ \\ \\mbox{(9)}<\/p>\n

Now we can re-arrange the terms but instead group by odd integers:<\/p>\n

\\displaystyle S_2(n) = (1)n + (3)(n-1) + (5)(n-2) + \\ldots + (2n-1)(1)
\n\\displaystyle \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ = \\sum_{k=0}^{n-1}(n-k)(2k+1)
\n\\displaystyle \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ = (2n-1)\\sum_{k=0}^{n-1}k - 2\\sum_0^{n-1}k^2 + \\sum_0^{n-1}n
\n\\displaystyle \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ =(2n-1)S_1(n-1) -2S_2(n-1) + n^2. \\ \\ \\ \\ \\ \\mbox{(10)}<\/p>\n

Note that both S_1 \\mbox{ and } S_2 occur in the recurrence, but we know already S_1 from (2)<\/a>. Substituting this gives our second recurrence in S_2 alone:<\/p>\n

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

\\displaystyle S_2(n) = n^3 - \\tfrac{1}{2}n^2 + \\tfrac{1}{2}n - 2S_2(n-1).\\ \\ \\ \\ \\ \\mbox{(11)}<\/p>\n

 <\/p>\n

Combining the two recurrences (8)<\/a> and (11)<\/a>, and simplifying, yields<\/p>\n

\\displaystyle 3S_2(n) = n^3 + \\tfrac{3}{2}n^2 + \\tfrac{1}{2}n,<\/p>\n

from which the closed form formula is immediate:
\n<\/a><\/p>\n

\\displaystyle S_2(n) = \\tfrac{1}{6}(2n^3 + 3n^2 + n) = \\tfrac{1}{3}n^3 + \\tfrac{1}{2}n^2 + \\tfrac{1}{6}n.\\ \\ \\ \\ \\ \\mbox{(12)}<\/p>\n

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

 <\/p>\n

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

4. Sum of Cubes<\/h3>\n

The recurrence relation approach to solving the two specific problems above suggests this may generalize to solving the general problem:<\/p>\n

\\displaystyle S_r(n) = \\sum_1^n k^r.<\/p>\n

Let’s test this theory by applying it to the sum of cubes problem:<\/p>\n

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

\\displaystyle S_3(n) = \\sum_1^n k^3.<\/p>\n

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

 <\/p>\n

<\/a> The first recurrence is: <\/a><\/p>\n

\\displaystyle S_3(n) = S_3(n-1) + n^3 \\ \\ \\ \\ \\ \\mbox{(13)}<\/p>\n

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

 <\/p>\n

<\/a> For the second recurrence, solve for k^3 in the solution for S_2(n), equation (12)<\/a> above:<\/p>\n

\\displaystyle 6S_2(k) = 2k^3 + 3k^2 + k<\/p>\n

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

\\displaystyle k^3 = 3S_2(k) - \\tfrac{3}{2}k^2 - \\tfrac{1}{2}k.\\ \\ \\ \\ \\ (14)<\/p>\n

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

 <\/p>\n

<\/a> Putting this into the definition (3)<\/a> gives: <\/a><\/p>\n

\\displaystyle S_3(n) = \\sum_1^n [3S_2(k) - \\tfrac{3}{2}k^2 - \\tfrac{1}{2}k]
\n\\displaystyle \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ = 3\\sum_1^n S_2(k) - \\tfrac{3}{2}\\sum_1^n k^2 - \\tfrac{1}{2}\\sum_1^n k
\n\\displaystyle \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ = 3\\sum_1^n S_2(k) - \\tfrac{3}{2}S_2(n) - \\tfrac{1}{2}S_1(n).\\ \\ \\ \\ \\ \\mbox{(15)}<\/p>\n

What is \\sum_1^n S_2(k)? Writing it out and then gathering like terms gives:<\/p>\n

\\displaystyle \\sum_1^n S_2(k) = S_2(1) + S_2(2) + S_2(3) + \\ldots + S_2(n)
\n\\displaystyle \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ = 1^2 + (1^2 + 2^2) + (1^2 + 2^2 + 3^2) + \\ldots + (1^2 + 2^2 + \\ldots + n^2)
\n\\displaystyle \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ = n(1^2) + (n-1)(2^2) + (n-2)(3^2) + \\ldots + 2(n-1)^2 + n^2
\n\\displaystyle \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ = \\sum_0^{n-1}(n-k)(k+1)^2
\n\\displaystyle \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ = \\sum_0^{n-1}[-k^3 + (n-2)k^2 + (2n-1)k + n]
\n\\displaystyle \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ = -S_3(n-1) + (n-2)S_2(n-1) + (2n-1)S_1(n-1) + n^2.\\ \\ \\ \\ \\ \\ (16)<\/p>\n

Putting (16) into (15)<\/a> gives the desired recurrence for S_3(n):
\n<\/a><\/p>\n

\\displaystyle S_3(n) = 3[-S_3(n-1) + (n-2)S_2(n-1) + (2n-1)S_1(n-1) + n^2] - \\tfrac{3}{2}S_2(n) - \\tfrac{1}{2}S_1(n).\\ \\ \\ \\ \\ (17)
\nRewriting (13)<\/a> for S_3(n-1), substituting into the above, and gathering like terms gives the closed form formula:<\/p>\n

4S_3(n) = 3n^3 + (3n-6)S_2(n-1) + (6n-3)S_1(n-1) + 3n^2 - \\tfrac{3}{2}S_2(n) - \\tfrac{1}{2}S_1(n).<\/p>\n

Substitute with known formulae for S_2(n-1) and S_1(n-1), equations (2) and (12), to get after algebraic simplification:
\n<\/a><\/p>\n

\\displaystyle S_3(n) = \\tfrac{1}{4}(n^4 + 2n^3 + n^2) = \\tfrac{1}{4}n^4 + \\tfrac{1}{2}n^3 + \\tfrac{1}{4}n^2.\\ \\ \\ \\ \\ (18)<\/p>\n

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

 <\/p>\n

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

A table of the first few values is<\/p>\n

\\displaystyle n: 1,2,3,4,5,6\\ldots<\/p>\n

\\displaystyle S_3(n): 1,9,36,100,225,441\\ldots<\/p>\n

5. Sum of Quartics — S_4(n) = \\sum_1^n k^4<\/h3>\n

Sum of quartics S_4(n) can now be handled routinely:<\/p>\n

First recurrence: <\/a><\/p>\n

\\displaystyle S_4(n) = S_4(n-1) + n^4.\\ \\ \\ \\ \\ (19)<\/p>\n

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

 <\/p>\n

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

Second recurrence: Start with the solution to S_3(n), equation (18)<\/a>, and solve for n^4:<\/p>\n

\\displaystyle n^4 = 4S_3(n) - 2n^3 - n^2. \\ \\ \\ \\ \\ (20)<\/p>\n

Substitute (20) into definition (2)<\/a>:<\/p>\n

\\displaystyle S_4(n) = \\sum_1^n k^4 = \\sum_1^n [4S_3(k) - 2k^3 - k^2]
\n\\displaystyle \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ = 4\\sum_1^n S_3(k) - 2\\sum_1^n k^3 - \\sum_1^n k^2
\n\\displaystyle \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ = 4\\sum_1^n S_3(k) - 2S_3(n) - S_2(n)
\n[Writing out the first sum and gathering like cubes gives:]
\n<\/a>= 4[\\sum_0^{n-1} (n-k)(k+1)^3] - 2S_3(n) - S_2(n)
\n\\displaystyle \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ = 4[-S_4(n-1) + (n-3)S_3(n-1) + (3n-3)S_2(n-1) + \\ldots
\n\\displaystyle \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ldots + (3n-1)S_1(n-1) + n^2] - 2S_3(n) - S_2(n),\\ \\ \\ \\ \\ (21)<\/p>\n

which is the desired second recurrence.<\/p>\n

Rewriting (19)<\/a> for S_4(n-1) and substituting into the above yields the closed form formula:
\n<\/a><\/p>\n

\\displaystyle S_4(n) = \\tfrac{1}{5}[4n^4 + 4(n-3)S_3(n-1) + 4(3n-3)S_2(n-1) \\ldots
\n\\displaystyle \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ldots + 4(3n-1)S_1(n-1) + 4n^2 - 2S_3(n) - S_2(n)]<\/p>\n

which after algebraic simplification, is:
\n<\/a><\/p>\n

\\displaystyle S_4(n) = \\tfrac{1}{30}(6n^5 + 15n^4 + 10n^3 - n) = \\tfrac{1}{5}n^5 + \\tfrac{1}{2}n^4 + \\tfrac{1}{3}n^3 -\\tfrac{1}{30}n \\\\ \\ \\ \\ \\ (22)<\/p>\n

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

 <\/p>\n

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

A table of the first few values is<\/p>\n

\\displaystyle n: 1,2,3,4,5,6\\ldots<\/p>\n

\\displaystyle S_4(n): 1,17,98,354,979,2275\\ldots<\/p>\n

Using a Symbolic Computation package<\/h4>\n

A computational algebra system such as Maxima, Maple, Mathematica, or Sage, can handle hairy algebraic simplifications such as the one in (4 SOL SYMB)<\/a> quite easily. See Figure 3<\/a>, which shows a typical result using the Maxima software — available freely.[Max09<\/a>] To find out how Maxima is able to handle complicated symbolical algebra, see [PWZ<\/a>].<\/p>\n

\"Symbolic<\/a>

Symbolic Simplification in Maxima<\/p><\/div>\n

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

6. Next Steps: The General Case<\/h4>\n

Applying the method above to the general case S_r(n) = \\sum_{k=1}^n k^r yields the r-th order recurrence relation:
\n<\/a><\/p>\n

\\displaystyle S_r(n) = \\frac{1}{1+\\alpha_{r-1}(r)}\\left(n^2 + n^r + \\sum_{j=1}^{r-1} C_{r-1}(j)S_j(n-1) - \\sum_{j=1}^{r-1} \\alpha_{r-1}(j) S_j(n)\\right), \\ \\ \\ \\ \\ (23)<\/p>\n

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

 <\/p>\n

<\/a> where \\alpha_{r-1}(j) is the coefficient of n^j in the polynomial solution to S_{r-1}(n), and<\/p>\n

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

The details of this derivation and its solution are given in Finite Summations, Part 2<\/em><\/a> of this paper, [Ebr10a<\/a>].<\/p>\n

To obtain a direct (non-iterative) general solution to S_r(n) requires a different approach. In Part 3 of this paper<\/a>, [EO10<\/a>], we use a matrix method and a linear independence argument from linear algebra to obtain a general closed form solution.<\/p>\n

7. Conclusion and Commentary<\/h3>\n

Summary<\/h4>\n

In the above discussion, we have motivated and illustrated an bootstrap method using recurrence relations that yields closed form formulas for finite summations of any integer power in terms of lower order finite summations.<\/p>\n

The closed form formulas for the first four powers were developed to motivate the approach and illustrate the method:<\/p>\n

\\displaystyle S_1(N) = \\sum_{k=1}^n k = \\tfrac{1}{2}(n^2+n)<\/p>\n

\\displaystyle S_2(n) = \\sum_{k=1}^n k^2 = \\tfrac{1}{6}(2n^3+3n^2+n)<\/p>\n

\\displaystyle S_3(n) = \\sum_{k=1}^n k^3 = \\tfrac{1}{4}(n^4+2n^3+n^2)<\/p>\n

\\displaystyle S_4(n) = \\sum_{k=1}^n k^4 = \\tfrac{1}{30}(6n^5 + 15n^4 + 10n^3 - n)<\/p>\n

Using this method, one can obtain the closed form formulas for any finite sum of integral powers.<\/p>\n

Observations<\/h4>\n

Observe the coefficients of the polynomial solution to S_r(n) sum to unity. This is a necessary condition due to S_r(1) = 1 for all r, hence any polynomial in n must have coefficients summing to 1.<\/p>\n

The highest order coefficient is the integral of k^r, i.e. \\tfrac{1}{r+1}.<\/p>\n

The next coefficient is always \\tfrac{1}{2}.<\/p>\n

Problems<\/h4>\n
    \n
  1. Show that the sum of first n odd integers sums to n^2. Use Method 1.<\/li>\n<\/ol>\n

    Acknowledgements<\/h4>\n

    I thank Carol Ouellette for reading an early draft of this paper and for many thoughtful comments and suggestions.<\/p>\n

    \n

    This article is available for download as a PDF here<\/a>.<\/p>\n

    >> Continue reading: <\/em>Sums of Powers x^r, Part 2<\/a><\/p>\n

    >> Continue reading: <\/em>Sums of Powers x^r, Part 3<\/a><\/p>\n

    >> Continue reading: <\/em>Good Mathematical Technique and the Case for Mathematical Insight<\/a><\/p>\n

    \n

    References<\/h3>\n
    \n
    [Ebr10a]<\/a><\/dt>\n
    Sums of Powers xr<\/sup>, part 2.<\/a>
    \nAssad Ebrahim.
    \nFebruary 2010.<\/dd>\n<\/dl>\n

    [EO10]<\/a>Sums of Powers xr<\/sup>, part 3.<\/a>
    \nAssad Ebrahim and Carol Ouellette.
    \nApril 2010.<\/p>\n

    [Hay06]<\/a>Gauss’s day of reckoning.
    \nBrian Hayes.
    \nThe American Scientist, Vol. 94, No. 3<\/em>, page 200, May\/June
    \n2006.<\/p>\n

    [Max09]<\/a>Maxima, a Computer Algebra System<\/em>.
    \n2009.<\/p>\n

    [PWZ96]<\/a>A=B<\/em>.
    \nMarko Petkovsek, Herbert Wilf, and Doron Zeilberger.
    \n1996, AK Peters\/CRC Press<\/p>\n

    \n

    Footnotes<\/h3>\n

    <\/p>\n

    \n
    <\/div>\n
      \n
    1. In actuality, despite being part of the handed down tradition of every mathematician, the attribution of this problem and solution to the historical Gauss seems to be apocryphal. Investigative reporter Brian Hayes (Hay06<\/a>) was not able to find any primary historical source giving the problem, let alone the solution method. The only primary historical source that provides any mention at all merely gave an anecdote that Gauss was mathematical precocious at an early age, and that in one particular instance he surprised even the instructor with how swiftly he was able to dispatch with an assigned problem. ↩<\/a><\/span><\/li>\n
    2. We also get the relation: n^2 = 2S_1(n-1) + n, interpreted as the square n^2 is composed of the diagonal n plus the two red triangles S_1(n-1) above and below the diagonal. From this we get S_1(n-1) = \\frac{1}{2}(n^2 - n) so
      \n\\displaystyle S_1(n) = \\frac{1}{2}( (n+1)^2 - (n+1) ) = \\frac{1}{2}( n^2 + 2n +1 - n - 1) = \\frac{1}{2}(n^2 +n), as shown before.       ↩<\/a><\/span><\/li>\n
    3. The first few odd integers can be written as M odd integers:\n

      \\displaystyle S_{1_{\\mbox{odd}}}(M)=\\sum_0^M 2k+1 = 1+3+5+\\ldots+(2M+1)<\/p>\n

      or restricted to only odd integers while sum runs from 1 to n, in which case the equivalent value M = \\lfloor \\tfrac{n-1}{2} \\rfloor.<\/p>\n

      Closed form formulas are:<\/p>\n

      \\displaystyle S_{1_{\\mbox{odd}}}(M) = (M+1)^2,<\/p>\n

      or<\/p>\n

      \\displaystyle S_{1_{\\mbox{odd}}}(n) = \\left(\\left\\lfloor \\tfrac{n-1}{2} \\right\\rfloor + 1 \\right)^2 = \\left\\lfloor \\tfrac{n+1}{2} \\right\\rfloor^2.<\/p>\n

      ↩<\/a><\/span><\/li>\n

    4. If there is a moral to this story, it is that in mathematics, play around, stay curious and alert, and pursue interesting observations when they arise — they often turn out to be useful. ↩<\/a><\/span><\/li>\n<\/ol>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

      2nd ed. January 21, 2018; 1st ed. Feb 8th, 2010<\/p>\n

      Abstract This three part paper explores solving the sum of powers problem using discrete maths techniques (recurrence relations, matrix systems) to obtain a solution polynomials whose coefficients turn out to be exactly the Bernoulli numbers . Part 1 (this paper) solves the problem using recurrence [Read More…]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"nf_dc_page":"","footnotes":""},"categories":[119],"tags":[25,26,28,23,29,27],"coauthors":[112],"class_list":["post-585","post","type-post","status-publish","format-standard","hentry","category-technical","tag-discrete-mathematics","tag-finite-summation","tag-heuristics","tag-maxima","tag-problem-solving","tag-results","odd"],"views":54515,"_links":{"self":[{"href":"https:\/\/mathscitech.org\/articles\/wp-json\/wp\/v2\/posts\/585","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mathscitech.org\/articles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mathscitech.org\/articles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mathscitech.org\/articles\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mathscitech.org\/articles\/wp-json\/wp\/v2\/comments?post=585"}],"version-history":[{"count":248,"href":"https:\/\/mathscitech.org\/articles\/wp-json\/wp\/v2\/posts\/585\/revisions"}],"predecessor-version":[{"id":11609,"href":"https:\/\/mathscitech.org\/articles\/wp-json\/wp\/v2\/posts\/585\/revisions\/11609"}],"wp:attachment":[{"href":"https:\/\/mathscitech.org\/articles\/wp-json\/wp\/v2\/media?parent=585"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mathscitech.org\/articles\/wp-json\/wp\/v2\/categories?post=585"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mathscitech.org\/articles\/wp-json\/wp\/v2\/tags?post=585"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/mathscitech.org\/articles\/wp-json\/wp\/v2\/coauthors?post=585"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}