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

**Abstract**

This paper uses recurrence relations to solve the sum-of-powers problem for small . A recursive solution to the general case (arbitrary ) 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 for:

and, generally:

### 2. Solving Linear Sums

#### Method 1: Algebraic Insight

Tradition^{1} 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:

The left hand terms add to , or twice the original. Each of the right-hand terms adds to and there are exactly terms, giving the solution:

.

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

Arranging each term as a row of dots forms a right triangle (Figure 1, blue dots) with side lengths and a diagonal each of dots. is the total number of dots in the triangle, hence the name **triangular numbers** for .

Finding the desired sum , 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 dots, and removing the diagonal ( dots), which leaves two (red) triangles of side length , , each having half the remaining dots, or

.

We can now shift indices to get the solution as before:

Note that this geometric deconstruction also yields recurrence that will be fundamental:

which says the blue triangle is the red triangle with the diagonal 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:

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 .

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

This says that the blue triangle remains after removing a smaller copy, the red triangle, from the square of 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:

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 , 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 by prescribing an automatic way of generating the second recurrence using a generalization of the geometric insight of solution 2.

### 3. Sum of Squares

The sequence for goes as:

Method 1 doesn’t work for : matched pairs from opposite ends of the finite sum don’t have a constant sum (92, 60, 44 for ).

Playing with dot arrangements yields a pattern: each square number is built up as a sum of the first 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}

#### Method 3: Two Recurrence Relations

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

For the second recurrence relation write out the definition of and replace each term using the Sum-of-Odd-Integers-is-Square Lemma (e.g. ). This gives:

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

Note that both occur in the recurrence, but we know already from (2). Substituting this gives our second recurrence in alone:

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

from which the closed form formula is immediate:

### 4. Sum of Cubes

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

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

For the second recurrence, solve for in the solution for , equation (12) above:

Putting this into the definition (3) gives:

What is ? Writing it out and then gathering like terms gives:

Putting (16) into (15) gives the desired recurrence for :

Rewriting (13) for , substituting into the above, and gathering like terms gives the closed form formula:

Substitute with known formulae for and , equations (2) and (12), to get after algebraic simplification:

A table of the first few values is

### 5. Sum of Quartics —

Sum of quartics can now be handled routinely:

Second recurrence: Start with the solution to , equation (18), and solve for :

Substitute (20) into definition (2):

[Writing out the first sum and gathering like cubes gives:]

which is the desired second recurrence.

Rewriting (19) for and substituting into the above yields the closed form formula:

which after 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].

#### 6. Next Steps: The General Case

Applying the method above to the general case yields the -th order recurrence relation:

where is the coefficient of in the polynomial solution to , and

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 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:

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 sum to unity. This is a necessary condition due to for all , hence any polynomial in must have coefficients summing to 1.

The highest order coefficient is the integral of , i.e. .

The next coefficient is always .

#### Problems

- Show that the sum of first odd integers sums to . 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 , Part 2

*>> Continue reading: *Sums of Powers , 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: , interpreted as the square is composed of the diagonal plus the two red triangles above and below the diagonal. From this we get so

, as shown before. ↩ - The first few odd integers can be written as odd integers:
or restricted to only odd integers while sum runs from 1 to , in which case the equivalent value .

Closed form formulas are:

or

- 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