(Discrete Mathematics Techniques I)
Abstract
We motivate an approach that uses recurrence relations to find closed form solutions to the finitesummationofintegerpowers problem for any individual . The approach is illustrated for small : . Maxima, an opensource (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 ) is developed in Part 2 along with Maxima source code. A direct (noniterative) 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:
In particular, we want closed form solutions (formulas in ) for the following finite summations:
and, generally:
1.2. Dispatching
Let’s look at the finite summation:
How to find a closed form formula for this summation?
Solution Method 1: Numerical Insight
If you’re seven year old Gauss, the story goes^{1} that you knock off (1) with the following insight: expand out the summation twice, once in forward order and once in reverse order:
Add the righthand sides of (i) and (ii) in columnwise fashion. Observe that columnwise sums are uniformly and that there are exactly 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 , and the closed form formula for (1) is therefore
.
Elegant. But suppose you’re not Gauss. Is there another way?
Solution Method 2: Geometric Arrangement
Write out the first few terms of , and the corresponding sums for
Playing about with the numbers, perhaps you spot a pattern? Write out as dots aligned on successive rows. They form an isosceles right triangle (the blue triangle in Figure 1) having side length and a diagonal of dots.
But the desired sum, the blue triangle, is part of a square of side length having dots. Taking away the diagonal of dots leaves two subdiagonal triangles, like the red one, having half the remaining dots: . Adding back the dots on the diagonal gives the solution (blue triangle) as
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 , namely:
(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 and . 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 remains after removing a smaller copy, the red triangle, from the square of dots.^{2} This gives a second recurrence:
So now we have our two desired equations: (1A), (1B). Solving (1B) for , substituting this into (1A), and gathering like terms gives the equation
from which the solution (1 SOL) is immediate.
PostMortem 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
(P1)
Find a closed form formula for this summation.
The sequence for goes as:
Solution Method 1 for 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.^{3}
Lemma: Sum of odd integers
The sum of odd integers from 1 to is a square number. To see this, arrange dots like so:
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.^{4}Solution Method 3: Recurrence Relations
As before, a first recurrence relation is immediate from definition (2):
We get a second recurrence relation by writing out and writing each in a different way, using the Sum of Odd Integers lemma.
There are terms in this sum. Gathering terms by like odd integers:
[Recognize: first and second sums are the lower order summations ]
This gives a recurrence for in terms of and . Substituting in the closed form formula (1 SOL) solved yields the desired second recurrence for :
Rewriting (2A) for , inserting this into (2B), and simplifying, yields
from which the closed form formula is immediate:
1.4. Finding
The recurrence relation approach to solving the two specific problems above suggests this may generalize to solving the general problem:
Let’s test the general approach by attacking
We’ll find the second recurrence by writing in a different way using the closed form solution to in (2 SOL) above. Recall
So
Putting this into (3) gives:
What is ? Writing it out and then gathering like terms gives:
which is a recurrence. Putting this into (3B) gives the desired second recurrence relation for , with other lowerorder recurrences for which we have already found the closed form formulas:
Rewriting (3A) for , substituting into the above, and gathering like terms gives the closed form formula:
from which the solution, after (some slightly hairy) algebraic simplification, is:
A table of the first few values is
1.5. Finding
Armed with the foregoing, and using the more general notation
we can now calculate summarily: Let
Get the second recurrence from the term in the formula for , (3 SOL) above:
Inserting this into the definition (4):
[Writing out the first sum and gathering like cubes gives:]
, which is the desired second recurrence.
Rewriting the first recurrence (4A) for and substituting into the above yields the closed form formula in terms of lower order summations for which we already have closed form formulas:
The result, after (much more hairy) algebraic simplification, is:
A table of the first few values is
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].
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:
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 yields the th order recurrence relation (P SOL) that requires a different method to obtain the closed form solution.
where are the coefficients from the closed form solution of , and
The details of this derivation and its solution are given in Finite Summations, Part 2 of this paper, [Ebr10a].
To obtain a direct (noniterative) general solution to 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.
Epilogue: Mathematical Insight? or Good Technique?
The mathematician Alfred North Whitehead^{5} observed that
[Advancement occurs]^{6} 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 finitesummationofintegerpowers 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 , Part 2
>> Continue reading: Finite Summations of Integer Powers , Part 3
>> Continue reading: Good Mathematical Technique and the Case for Mathematical Insight
References
 [Ebr10a]

Finite summation of integer powers x^{p}, part 2.
Assad Ebrahim.
February 2010.  [EO10]

Finite summation of integer powers x^{p}, 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: , interpreted as the number of dots in the square is composed of two right triangles not including the diagonal, hence of side length , 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 odd integers:
Or we can take the odd integers from 1 to , in which case .
Closed form formulas are then:
or
 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. ↩
Leave a Reply