Finite Summation of Integer Powers (Part 1)

By Assad Ebrahim, on February 8th, 2010
Topic: Mathematics-Technical

(Discrete Mathematics Techniques I)

Abstract
We motivate an approach that uses recurrence relations to find closed form solutions to the finite-summation-of-integer-powers problem ${S_p(N) = \sum_{k=1}^{N} k^p}$ for any individual ${p}$ . The approach is illustrated for small ${p}$ : ${k, k^2, k^3, k^4}$ . Maxima, an open-source (free) software package, is used to demonstrate how a symbolic computation platform can speed up the accurate derivation of messy algebraic expressions.

A recurrence solution to the general case (arbitrary $p$ ) is developed in Part 2 along with Maxima source code. A direct (non-iterative) matrix method for solving the general case is given in Part 3 along with Maxima and Octave/Matlab source code.

1. Developing Technique, Specific Examples

Introduction

We are looking for closed form formulas for a family of summations of powers of integers: ${\sum_{k=1}^{N} k^p}$

In particular, we want closed form solutions (formulas in ${N}$ ) for the following finite summations:

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

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

$\displaystyle \sum_{k=1}^{N} k^3\ \ \ \ \ (3)$

$\displaystyle \sum_{k=1}^{N} k^4\ \ \ \ \ (4)$

and, generally:

$\displaystyle \sum_{k=1}^{N} k^p = 1^p + 2^p + 3^p + \ldots + (N-1)^p + N^p\ \ \ \ \ (P)$

1.2. Dispatching ${S_1(N) = \sum_{k=1}^N k}$

Let’s look at the finite summation:

$\displaystyle S_1(N) = \sum_1^N k\ \ \ \ \ (1)$

How to find a closed form formula for this summation?

Solution Method 1: Numerical Insight

If you’re nine year old Gauss, the story goes¹ that you knock off (1) with the following insight: expand out the summation twice, once in forward order and once in reverse order:
$\sum_1^N k = 1 + 2 + 3 + \ldots + (N-2) + (N-1) + N\ \ \ \ \ \mbox{(i)}$

$\sum_1^N k = N + (N-1) + (N-2) + \ldots + 3 + 2 + 1.\ \ \ \ \ \mbox{(ii)}$
Add the right-hand sides of (i) and (ii) in column-wise fashion. Observe that column-wise sums are uniformly ${N+1}$ and that there are exactly ${N}$ copies of these. But the second equation is a duplicate copy of the original summation, so the result must be twice the original sum. So it follows that ${2S_1(N) = N(N+1)}$ , and the closed form formula for (1) is therefore

$\displaystyle S_1(N) = \tfrac{1}{2}(N+1)N$

$\displaystyle \ \ \ \ \ \ \ \ \ \ \ = \tfrac{1}{2}[N^2 + N] \ \ \ \ \ \mbox{(1 SOL)}$ .

Elegant. But suppose you’re not Gauss. Is there another way?

Solution Method 2: Geometric Arrangement

Write out the first few terms of ${S_1(N) = \sum_1^N k}$ , and the corresponding sums for ${N = 1,2,3,\ldots}$

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

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

Playing about with the numbers, perhaps you spot a pattern? Write out ${\{1,2,3,4,\ldots\}}$ as dots aligned on successive rows. They form an isosceles right triangle (the blue triangle in Figure 1) having side length ${N}$ and a diagonal of ${N}$ dots.

S_1(N) is the blue triangle

But the desired sum, the blue triangle, is part of a square of side length ${N}$ having ${N^2}$ dots. Taking away the diagonal of ${N}$ dots leaves two sub-diagonal triangles, like the red one, having half the remaining dots: ${\tfrac{1}{2}(N^2 - N)}$ . Adding back the ${N}$ dots on the diagonal gives the solution (blue triangle) as

$\displaystyle S(N)=\tfrac{1}{2}[N^2 + N],$

which is as before.

Good. But again some insight was necessary. Let’s look at a third method, the one that will give us good mileage for the remaining problems in the family.

Solution Method 3: Recurrence Relations

The definition (1) gives a first recurrence relation for ${S(N)}$ , namely:

$\displaystyle S(N) = S(N-1) + N\ \ \ \ \ \mbox{(1A)}$

(This says that you get from one sum to the next case by adding the next term.) But this can also be regarded as an equation in two unknowns ${S(N)}$ and ${S(N-1)}$ . So, by analogy with linear equations, let’s look for another recurrence — if we have two we should be able to solve by substitution.

From where can we get a second recurrence? A little insight is needed at this point. Consider the arrangement of dots in Figure 1 above: observe that the blue triangle ${S(N)}$ remains after removing a smaller copy, the red triangle, ${S(N-1)}$ from the square of ${N^2}$ dots.² This gives a second recurrence:

$\displaystyle S(N) = N^2 - S(N-1)\ \ \ \ \ \mbox{(1B)}$

So now we have our two desired equations: (1A), (1B). Solving (1B) for ${S(N-1)}$ , substituting this into (1A), and gathering like terms gives the equation

$\displaystyle 2S(N) = N^2 + N,$

from which the solution (1 SOL) is immediate.

Post-Mortem Commentary What was required to obtain the solution to (1) using each of the three methods?

The first solution method required the observation that the pairs with entries marching in from opposite sides have a constant sum. Rewriting the series twice dealt with the sticky detail of 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. The challenge was in finding the second recurrence, which required some insight. In this case, the geometric arrangement of solution method 2 suggested the second recurrence, after which obtaining the solution was mechanical.

Claim: No Further Insight Necessary

So, although an insight was needed to solve this first problem in the family using each of the solution methods, I claim that with the appropriate technique (recurrences) and the solution we have just found, the remaining problems in the family can be solved without further requiring insight.

1.3. Finding ${S_2(N) = \sum_1^N k^2}$

(P-1)

Consider the finite summation

$\displaystyle T(N) = \sum_1^N k^2\ \ \ \ \ (2)$

Find a closed form formula for this summation.

The sequence for ${T(N)}$ goes as:

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

$\displaystyle T(N): 1,5,14,30,55,91,\ldots$

Solution Method 1 for ${S_1(N)}$ doesn’t yield a useful insight: pairs marching in from the ends don’t have a constant sum. Solution Method 2 does not provide an insight for a solution (no obvious geometric arrangement of partial sums using dots). However, playing with dot arrangements does yield an interesting pattern. Pursuing it yields a Lemma that will turn out to give us a second recurrence relation, allowing us to use Solution Method 3.³

Lemma: Sum of odd integers

The sum of odd integers from 1 to ${N}$ is a square number. To see this, arrange dots like so:

Sum of Odd Integers

The closed form formula requires fixing some notation, and so is awkward. But since it is not used in closed form, it is given in the footnote for reference.⁴

Solution Method 3: Recurrence Relations

As before, a first recurrence relation is immediate from definition (2):

$\displaystyle T(N) = T(N-1) + N^2.\ \ \ \ \ \mbox{(2A)}$

We get a second recurrence relation by writing out ${T(N)}$ and writing each ${k^2}$ in a different way, using the Sum of Odd Integers lemma.

$\displaystyle T(N) = 1^2 + 2^2 + 3^2 + \ldots + N^2$

$\displaystyle \ \ \ \ \ \ \ \ \ \ = (1) + (1+3) + (1+3+5) + \ldots + (1+3+5+\ldots+(2N-1))$

There are ${N}$ terms in this sum. Gathering terms by like odd integers:

$\displaystyle T(N) = N(1) + (N-1)3 + (N-2)5 + \ldots + 1(2N-1)$

$\displaystyle \ \ \ \ \ \ \ \ \ \ = \sum_0^{N-1}(N-k)(2k+1)$

$\displaystyle \ \ \ \ \ \ \ \ \ \ = (2N-1)\sum_0^{N-1}k - 2\sum_0^{N-1}k^2 + \sum_0^{N-1}N$

[Recognize: first and second sums are the lower order summations $S(N-1), T(N-1)$ ]

$\displaystyle \ \ \ \ \ \ \ \ \ \ =(2N-1)S(N-1) -2T(N-1) + N^2,$

This gives a recurrence for ${T(N)}$ in terms of ${S(N-1)}$ and ${T(N-1)}$ . Substituting in the closed form formula (1 SOL) solved ${S(N-1)}$ yields the desired second recurrence for ${T(N)}$ :

$\displaystyle T(N) = N^3 - \tfrac{1}{2}N^2 + \tfrac{1}{2}N - 2T(N-1).\ \ \ \ \ \mbox{(2B)}$

Rewriting (2A) for ${T(N-1)}$ , inserting this into (2B), and simplifying, yields

$\displaystyle 3T(N) = N^3 + \tfrac{3}{2}N^2 + \tfrac{1}{2}N,$

from which the closed form formula is immediate:

$\displaystyle T(N) = \tfrac{1}{6}(2N^3 + 3N^2 + N).\ \ \ \ \ \mbox{(2 SOL)}$

1.4. Finding ${S_3(N) = \sum_1^N k^3}$

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

$\displaystyle S_p(N) = \sum_1^N k^p.$

Let’s test the general approach by attacking

$\displaystyle U(N) = \sum_1^N k^3.\ \ \ \ \ (3)$

Recurrence 1 is:

$\displaystyle U(N) = U(N-1) + N^3 \ \ \ \ \ \mbox{(3A)}$

We’ll find the second recurrence by writing ${k^3}$ in a different way using the closed form solution to ${T(N)}$ in (2 SOL) above. Recall

$\displaystyle T(N) := \sum_1^N k^2 = \tfrac{1}{6}[2N^3 + 3N^2 + N].$

$\displaystyle 6T(K) = 2K^3 + 3K^2 + K$

and

$\displaystyle K^3 = 3T(K) - \tfrac{3}{2}K^2 - \tfrac{1}{2}K.\ \ \ \ \ (*)$

Putting this into (3) gives:

$\displaystyle U(N) = \sum_1^N [3T(K) - \tfrac{3}{2}K^2 - \tfrac{1}{2}K]$

$\displaystyle \ \ \ \ \ \ \ \ \ \ = 3\sum_1^N T(K) - \tfrac{3}{2}\sum_1^N K^2 - \tfrac{1}{2}\sum_1^N K$

$\displaystyle \ \ \ \ \ \ \ \ \ \ = 3\sum_1^N T(K) - \tfrac{3}{2}T(N) - \tfrac{1}{2}S(N).\ \ \ \ \ \mbox{(3B)}$

What is ${\sum_1^N T(K)}$ ? Writing it out and then gathering like terms gives:

$\displaystyle \sum_1^N T(K) = T(1) + T(2) + T(3) + \ldots + T(N)$

$\displaystyle \ \ \ \ \ \ \ \ \ \ = 1^2 + (1^2 + 2^2) + (1^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 \ \ \ \ \ \ \ \ \ \ = -U(N-1) + (N-2)T(N-1) + (2N-1)S(N-1) + N^2,$

which is a recurrence. Putting this into (3B) gives the desired second recurrence relation for ${U(N)}$ , with other lower-order recurrences for which we have already found the closed form formulas:

$\displaystyle U(N) = -3U(N-1) + 3(N-2)T(N-1) + 3(2N-1)S(N-1) + 3N^2 \ldots$
$\ldots - \tfrac{3}{2}T(N) - \tfrac{1}{2}S(N).$ Rewriting (3A) for ${U(N-1)}$ , substituting into the above, and gathering like terms gives the closed form formula:

$4U(N) = 3N^3 + (3N-6)T(N-1) + (6N-3)S(N-1) + 3N^2 - \tfrac{3}{2}T(N) - \tfrac{1}{2}S(N)$

from which the solution, after (some slightly hairy) algebraic simplification, is:

$\displaystyle U(N) = \tfrac{1}{4}(N^4 + 2N^3 + N^2) \ \ \ \ \ \mbox{(3 SOL)}$

A table of the first few values is

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

$\displaystyle U(N): 1,9,36,100,225,441\ldots$

1.5. Finding ${S_4(N) = \sum_1^N k^4}$

Armed with the foregoing, and using the more general notation

$\displaystyle S_1(N) := S(N); \ \ S_2(N) := T(N); \ \ S_3(N) := U(N),$

we can now calculate ${S_4(N)}$ summarily: Let

$\displaystyle S_4(N) = \sum_1^N k^4\ \ \ \ \ (4)$

First recurrence:

$\displaystyle S_4(N) = S_4(N-1) + N^4.\ \ \ \ \ (4A)$

Get the second recurrence from the ${N^4}$ term in the formula for ${S_3(N)}$ , (3 SOL) above:

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

Inserting this into the definition (4):

$\displaystyle S_4(N) = \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)\ \ \ \ \ \mbox{(4B)}$

, which is the desired second recurrence.

Rewriting the first recurrence (4A) for ${S_4(N-1)}$ and substituting into the above yields the closed form formula in terms of lower order summations for which we already have closed form formulas:

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

The result, after (much more hairy) algebraic simplification, is:

$\displaystyle S_4(N) = \tfrac{1}{30}(6N^5 + 15N^4 + 10N^3 - N) \ \ \ \ \ \mbox{(4 SOL SYMB)}$

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

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

Next Steps: The General Case (Parts 2 & 3)

Applying the method above to the general case ${S_p(N) = \sum_{k=1}^N k^p}$ yields the ${p}$ -th order recurrence relation (P SOL) that requires a different method to obtain the closed form solution.

$\displaystyle S_p(N) = \frac{1}{1+\alpha_{p-1}(p)}\left(N^2 + N^p + \sum_{j=1}^{p-1} C_{p-1}(j)S_j(N-1) - \sum_{j=1}^{p-1} \alpha_{p-1}(j) S_j(N)\right), \ \ \ \ \ \mbox{(P SOL)}$

where ${\alpha_{p-1}(j)}$ are the coefficients from the closed form solution of ${S_{p-1}(N)}$ , and

$\displaystyle C_{p-1}(j) = \left[N\binom{p-1}{j} - \binom{p-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_p(N)$ requires a different approach. In Part 3 of this paper, [Ebr10b], we use a matrix method and a linear independence argument from linear algebra to obtain a general closed form solution.

Epilogue: Mathematical Insight? or Good Technique?

The mathematician Alfred North Whitehead⁵ observed that

[Advancement occurs]⁶ by extending the number of important operations which we can perform without thinking of them. (Introduction to Mathematics, 1911)

Mathematical Insight? or Good Technique? The finite-summation-of-integer-powers is an excellent elementary example for looking at this question.

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: Finite Summations of Integer Powers $x^p$ , Part 2

>> Continue reading: Finite Summations of Integer Powers $x^p$ , Part 3

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

References

[Ebr10a]

Assad Ebrahim.
Finite summation of integer powers x^p, part 2.
February 2010.

[Ebr10b]

Assad Ebrahim.
Finite summation of integer powers x^p, part 3.
February 2010.

[Hay06]

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

[Max09]

Maxima, a Computer Algebra System.
2009.

[PWZ]

Marko Petkovsek, Herbert Wilf, and Doron Zeilberger.
A=B.

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(N-1) + N}$ , interpreted as the number of dots in the square is composed of two right triangles not including the diagonal, hence of side length ${N-1}$ , with the diagonal thrown back in. ↩
There’s a moral in the story: pursue interesting observations — they often turn out to be useful. ↩
Defining the problem: We can take the first ${M}$ odd integers:
$\displaystyle S_o(M)=\sum_0^M 2k+1 = 1+3+5+\ldots+(2M+1)$

Or we can take the odd integers from 1 to ${N}$ , in which case ${M = \lfloor \tfrac{N-1}{2} \rfloor}$ .

Closed form formulas are then:
$\displaystyle S_o(M) = (M+1)^2,$

or
$\displaystyle S_o(N) = \left(\left\lfloor \tfrac{N-1}{2} \right\rfloor + 1 \right)^2 = \left\lfloor \tfrac{N+1}{2} \right\rfloor^2.$

↩
Whitehead was the major collaborator with Bertrand Russell in the strenuous 10 year attempt, ultimately unsuccessful, at driving through the logicist program in Mathematics, i.e. reducing the entire body of mathematics to a fixed system of logic. ↩
Whitehead claimed in the original that it is Civilization that advances in this way. I have reduced the claim for the purpose of this article. ↩