Sum of Integer Powers (Part 1)

By Assad Ebrahim, on January 21st, 2018 (52,043 views) | Leave your comment!
Topic: Maths--Technical

Spread the love

2nd ed. January 21, 2018; 1st ed. Feb 8th, 2010

Abstract
This 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$ .
Part 1 (this paper) solves the problem using recurrence relations in a way which a high school student could emulate for small $r$ . In Part 2, 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 discovered in 1713. In Part 3, 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.

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

1. Introduction

We are looking to find closed form solutions in $n$ for sums-of-powers problems:

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

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

$\displaystyle S_3(n) = \sum_{k=1}^{n} k^3\ \ \ \ \ \mbox{(cubes)}$

$\displaystyle S_4(n) = \sum_{k=1}^{n} k^4\ \ \ \ \ \mbox{(quarts)}$

and, generally:

$\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)}$

2. Solving Linear Sums

Consider the linear sum

$\displaystyle S_1(n) = \sum_{k=1}^{n} k = 1 + 2 + 3 + \ldots + (n-1) + n\ \ \ \ \ (1)$

Method 1: Algebraic Insight

Tradition¹ has it that seven-year-old Gauss solved (1) by writing out the sum twice, first forwards then in reverse, and then adding the terms column-wise:

$\displaystyle S_1(n) = 1 + 2 + 3 + \ldots + (n-2) + (n-1) + n$

$\displaystyle S_1(n) = n + (n-1) + (n-2) + \ldots + 3 + 2 + 1.$

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:

$\displaystyle 2S_1(n) = n(n+1) \implies S_1(n) = \tfrac{1}{2}n(n+1) = \tfrac{1}{2}[n^2 + n] \ \ \ \ \ (2)$ .

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?

Method 2: Geometric Insight

Write down the first few examples of (1):

$\displaystyle n: 1,2,3,4,5,6,\ldots$

$\displaystyle S_1(n): 1,3,6,10,15,21,\ldots$

S_1(n) is the blue triangle

Arranging each term $\{1,2,3,4,\ldots\}$ as a row of dots forms a right triangle (Figure 1, 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 for $S_1(n)$ .

Finding the desired sum $S_1(n)$ , the blue triangle, is now a geometric question, and there are several solutions.

Solution 2A 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
$\displaystyle S_1(n-1) = \tfrac{1}{2}(n^2 - n) = \tfrac{1}{2}(n-1)(n)$ .

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

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

Good. Here the insight was using of geometry to represent the sum.

We now show a third method which motivates the one we will use to find the general solution.

Method 3: Two Recurrence Relations

The definition (1) gives a first-order recurrence relation:

$\displaystyle S_1(n) = S_1(n-1) + n\ \ \ \ \ \mbox{(5)}$

This says that you get from one sum to the next case by adding the next term.
If 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)$ .

The geometric insight above (see Figure 1) can be adapted to yield a second recurrence:

$\displaystyle S_1(n) = n^2 - S_1(n-1)\ \ \ \ \ \mbox{(6)}$

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.²

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.

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

$\displaystyle 2S_1(n) = n^2 + n \ \implies \ S_1(n) = \frac{1}{2}n(n+1),$

which is the same solution as equation 4 above.

Remarks Let’s consider what we have just seen.

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.

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.

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.

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.

3. Sum of Squares

Consider the sum of squares

$\displaystyle S_2(n) = \sum_1^n k^2\ \ \ \ \ (7)$

The sequence for $S_2(n)$ goes as:

$\displaystyle n: 1,2,3,4,5,6\ldots$

$\displaystyle S_2(n): 1,5,14,30,55,91,\ldots$

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)$ ).

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. ³ We shall exploit this lemma (sum-of-odd-integers-is-square) to obtain the required second recurrence and solve the problem.⁴

Figure 2. Sum of Odd Integers

Method 3: Two Recurrence Relations

The first recurrence relation is immediate from the definition (2):

$\displaystyle S_2(n) = S_2(n-1) + n^2.\ \ \ \ \ \mbox{(8)}$

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:

$\displaystyle S_2(n) = 1^2 + 2^2 + 3^2 + \ldots + n^2$
$\displaystyle \ \ \ \ \ \ \ \ \ \ = (1) + (1+3) + (1+3+5) + \ldots + (1+3+5+\ldots+(2n-1))\ \ \ \ \ \mbox{(9)}$

Now we can re-arrange the terms but instead group by odd integers:

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

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

$\displaystyle S_2(n) = n^3 - \tfrac{1}{2}n^2 + \tfrac{1}{2}n - 2S_2(n-1).\ \ \ \ \ \mbox{(11)}$

Combining the two recurrences (8) and (11), and simplifying, yields

$\displaystyle 3S_2(n) = n^3 + \tfrac{3}{2}n^2 + \tfrac{1}{2}n,$

from which the closed form formula is immediate:

$\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)}$

4. Sum of Cubes

The recurrence relation approach to solving the two specific problems above suggests this may generalize to solving the general problem:

$\displaystyle S_r(n) = \sum_1^n k^r.$

Let’s test this theory by applying it to the sum of cubes problem:

$\displaystyle S_3(n) = \sum_1^n k^3.$

The first recurrence is:

$\displaystyle S_3(n) = S_3(n-1) + n^3 \ \ \ \ \ \mbox{(13)}$

For the second recurrence, solve for $k^3$ in the solution for $S_2(n)$ , equation (12) above:

$\displaystyle 6S_2(k) = 2k^3 + 3k^2 + k$

$\displaystyle k^3 = 3S_2(k) - \tfrac{3}{2}k^2 - \tfrac{1}{2}k.\ \ \ \ \ (14)$

Putting this into the definition (3) gives:

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

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

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

Putting (16) into (15) gives the desired recurrence for $S_3(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)$
Rewriting (13) for $S_3(n-1)$ , substituting into the above, and gathering like terms gives the closed form formula:

$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).$

Substitute with known formulae for $S_2(n-1)$ and $S_1(n-1)$ , equations (2) and (12), to get after algebraic simplification:

$\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)$

A table of the first few values is

$\displaystyle n: 1,2,3,4,5,6\ldots$

$\displaystyle S_3(n): 1,9,36,100,225,441\ldots$

5. Sum of Quartics — $S_4(n) = \sum_1^n k^4$

Sum of quartics $S_4(n)$ can now be handled routinely:

First recurrence:

$\displaystyle S_4(n) = S_4(n-1) + n^4.\ \ \ \ \ (19)$

Second recurrence: Start with the solution to $S_3(n)$ , equation (18), and solve for $n^4$ :

$\displaystyle n^4 = 4S_3(n) - 2n^3 - n^2. \ \ \ \ \ (20)$

Substitute (20) into definition (2):

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

which is the desired second recurrence.

Rewriting (19) for $S_4(n-1)$ and substituting into the above yields the closed form formula:

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

which after algebraic simplification, is:

$\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)$

A table of the first few values is

$\displaystyle n: 1,2,3,4,5,6\ldots$

$\displaystyle S_4(n): 1,17,98,354,979,2275\ldots$

Using a Symbolic Computation package

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

Symbolic Simplification in Maxima

6. Next Steps: The General Case

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

$\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)$

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

$\displaystyle C_{r-1}(j) = \left[n\binom{r-1}{j} - \binom{r-1}{j-1}\right].$

The details of this derivation and its solution are given in Finite Summations, Part 2 of this paper, [Ebr10a].

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

7. Conclusion and Commentary

Summary

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.

The closed form formulas for the first four powers were developed to motivate the approach and illustrate the method:

$\displaystyle S_1(N) = \sum_{k=1}^n k = \tfrac{1}{2}(n^2+n)$

$\displaystyle S_2(n) = \sum_{k=1}^n k^2 = \tfrac{1}{6}(2n^3+3n^2+n)$

$\displaystyle S_3(n) = \sum_{k=1}^n k^3 = \tfrac{1}{4}(n^4+2n^3+n^2)$

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

Using this method, one can obtain the closed form formulas for any finite sum of integral powers.

Observations

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.

The highest order coefficient is the integral of $k^r$ , i.e. $\tfrac{1}{r+1}$ .

The next coefficient is always $\tfrac{1}{2}$ .

Problems

Show that the sum of first $n$ odd integers sums to $n^2$ . Use Method 1.

Acknowledgements

I thank Carol Ouellette for reading an early draft of this paper and for many thoughtful comments and suggestions.

This article is available for download as a PDF here.

>> Continue reading: Sums of Powers $x^r$ , Part 2

>> Continue reading: Sums of Powers $x^r$ , Part 3

>> Continue reading: Good Mathematical Technique and the Case for Mathematical Insight

References

[Ebr10a]: Sums of Powers x^r, part 2.
Assad Ebrahim.
February 2010.

[EO10]Sums of Powers x^r, part 3.
Assad Ebrahim and Carol Ouellette.
April 2010.

[Hay06]Gauss’s day of reckoning.
Brian Hayes.
The American Scientist, Vol. 94, No. 3, page 200, May/June
2006.

[Max09]Maxima, a Computer Algebra System.
2009.

[PWZ96]A=B.
Marko Petkovsek, Herbert Wilf, and Doron Zeilberger.
1996, AK Peters/CRC Press

Footnotes

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) 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. ↩
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
$\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. ↩
The first few odd integers can be written as $M$ odd integers:
$\displaystyle S_{1_{\mbox{odd}}}(M)=\sum_0^M 2k+1 = 1+3+5+\ldots+(2M+1)$

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$ .

Closed form formulas are:

$\displaystyle S_{1_{\mbox{odd}}}(M) = (M+1)^2,$

or

$\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.$

↩
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. ↩

Mathematical Science & Technologies

Sum of Integer Powers (Part 1)

1. Introduction

2. Solving Linear Sums

Method 1: Algebraic Insight

Method 2: Geometric Insight

Method 3: Two Recurrence Relations

3. Sum of Squares

Method 3: Two Recurrence Relations

4. Sum of Cubes

5. Sum of Quartics — $S_4(n) = \sum_1^n k^4$

Using a Symbolic Computation package

6. Next Steps: The General Case

7. Conclusion and Commentary

Summary

Observations

Problems

Acknowledgements

References

Footnotes

Leave a Reply

Dear Readers:

Reading List…

Mathematics History & Philosophy

Topics in Mathematics: Pure & Applied Mathematics

Technology: Electronics & Embedded Computing

Technology: Sensors & Intelligent Systems

Maths Education

Explore…

Timeline

Mathematical Science & Technologies

Sum of Integer Powers (Part 1)

1. Introduction

2. Solving Linear Sums

Method 1: Algebraic Insight

Method 2: Geometric Insight

Method 3: Two Recurrence Relations

3. Sum of Squares

Method 3: Two Recurrence Relations

4. Sum of Cubes

5. Sum of Quartics —

Using a Symbolic Computation package

6. Next Steps: The General Case

7. Conclusion and Commentary

Summary

Observations

Problems

Acknowledgements

References

Footnotes

Leave a Reply

Dear Readers:

Reading List…

Mathematics History & Philosophy

Topics in Mathematics: Pure & Applied Mathematics

Technology: Electronics & Embedded Computing

Technology: Sensors & Intelligent Systems

Maths Education

Browse…

Explore…

Timeline

5. Sum of Quartics — $S_4(n) = \sum_1^n k^4$