Sums of Powers (Part 1)

New: updated January 21, 2018  (simplified, with added insights)

Abstract
This paper uses recurrence relations to solve the sum-of-powers problem S_r(n) = \sum_{k=1}^{n} k^r for small r=1,2,3,4. A recursive solution to the general case (arbitrary r) is developed in Part 2. A direct solution using matrix theory is given in Part 3. Source code is provided for all solutions.


1. Introduction

We are looking to solve a family of sums-of-powers, i.e. to find closed form formulas in n for:

\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

Tradition1 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

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

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

Sum of Odd Integers

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

so

\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

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

  1. 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 xr, part 2.
Assad Ebrahim.
February 2010.

[EO10]Sums of Powers xr, 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

  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) 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.
  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
    \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.
  3. 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.

  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.

Leave a Reply

  

  

  

Your comments are valued! (Please indulge the gatekeeping question as spam-bots cannot (yet) do simple arithmetic...) - required

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

Optionally add an image (JPEG only)

 

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