Sums and Differences of Discrete Functions

One of the many ways of expressing the sum of powers of the first n integers is in terms of binomial coefficients and either Eulerian numbers or Stirling numbers. The derivation of these formulas can best be described by an example. Consider the sequence of 5th powers of the integers 0, 1, 2, 3, … as shown below.

Now suppose we write a row beneath this sequence consisting of the differences between successive terms of this sequence, and then another row consisting of the differences between successive terms of that sequence, and so on. Likewise can write a row above the original sequence of 5th powers giving the cumulative sums of those numbers. Hence the fifth powers are the differences of this upper row. By the way, we are considering doubly-infinite sequences, with zeros to the left. Thus we have the rows of numbers shown below.

The elements of each row can be expressed as a linear combination of the elements of the row beneath it. For example, the next value on the top-most row would be 12201, which is the cumulative sum of the numbers in the next row, i.e., we have

Each of the numbers from the second row can likewise be expressed as cumulative sums of the numbers in the third row, as follows:

Thus, collecting the occurrences of the individual terms, we have

Repeating this process by expressing each number in parentheses as the cumulative sum of the numbers from the fourth row of the original table, we get

Consolidating the coefficients, this becomes

The coefficients of each row are therefore just the cumulative sums, from right to left, of the previous coefficients, and hence they are the binomial coefficients. Since the terms of each row are given by polynomials in the index, we are assured that eventually we will arrive at a row of constant differences beyond some point. For example, in the array above, the constant difference is 120. The next row will consist entirely of zeros, except for some leading non-zero terms. In the array above these leading terms are 1, 26, 66, 26, 1, which of course are the 5th row of the Eulerian numbers E_m,k, which can be defined by E_1,1 = 1 and the recurrence

The first few rows of the Eulerian numbers are listed below.

It follows that we can express any term in any of the rows above this row simply as a sum of binomial coefficients multiplied by these Eulerian numbers. To illustrate, by continuing the process described above, we arrive at

Thus the sum of the mth powers of the first n integers is

We also immediately have the more general result, giving the sums of the sums of the mth powers, and the sums of the sums of the sums of the mth powers, and so on. Letting s denote the number of cumulative summation levels, we have

Naturally these formulas with s = 0 simply give the sequence of mth powers themselves, and with s = 1 they give the familiar polynomials for sums of powers. For example, the sum of the 5th powers of the integers from 1 to n is given by

The original array of differences, which enables us to express the powers of the integers in terms of the Eulerian numbers in this way, also allows us to express the Eulerian numbers in terms of the powers of the first integers. As can be seen by inspection, the first Eulerian number on the mth row is 1, and the second is 2^m – (m+1). The third is

and so on, making use of the same kind of “sum of sums” pattern as we did previously. Thus the first three elements on the mth row can be written as

It’s easy to verify that this pattern continues, and in general the Eulerian numbers can be expressed in “closed form” as

In a sense, the Eulerian numbers play a role similar to the Dirac impulse function, in that they provide the finite impulse pattern which, when integrated a sufficient number of times, yields the sequences of pure powers, as well as all the cumulative sums.

An alternative way of expressing sums of powers can be gathered from looking again at the array of 5th powers and the differences. Notice the diagonal sequence of numbers highlighted in blue in the figure below.

These diagonal numbers represent the “discrete derivatives” of the cumulative sum of 5th powers (i.e., the first row) at n = 0, and we can express that function using the discrete analog of the Taylor series expansion, which is

where f ^(j) denotes the jth discrete derivative of f. The expressions f ^(j)(0)/(j-1)! are known as the Stirling numbers of the second kind, which we will denote by S_m,k, and the first several rows of them are tabulated below.

Therefore, letting f_m(n) denote the sum of the mth powers of the first n positive integers, we can write f_m(n) in the form

In addition to the recurrence relation

these Stirling numbers can also be expressed as a sum of binomial coefficients similar to the expression given above for the Eulerian numbers. We have

Inserting this into the expression for f_m(n), we get the “closed form” expression for the sum of the mth powers of the first n positive integers:

It’s worth noting that the techniques described above are not limited to just sequences of integer powers. We can immediately apply this approach to determine an expression for general sums of sums of an arbitrary polynomial or power series, or even any arbitrary function, although finite polynomials uniquely lead to finite expressions. As a simple example, consider the function

where the c_j are constants. Beginning with an infinite string of zeros to the left, the values of f(0), f(1), f(3), etc., are listing in the first row of the table below, followed by rows contain the differences between the terms of each successive row.

Using the three non-zero terms of the last row, we can write the sum

As with pure powers, we can express the sum of these sums, and so on, using essentially the same equation, but simply shifting the binomial coefficients.

Return to MathPages Main Menu