thesublimeblog

Science Bytes: Sums of Powers

I have a weakness for beautiful math formulae. If you share this admittedly nerdy interest, this post is for you, else just browse through or read my next post. 🙂

What I’m going to do today is share a powerful formula arising in number theory. The formula is (for nerds) a joy to behold. I will state the formula and the steps leading to it (which is beautiful in itself). You don’t to have a background in advanced math to understand the derivation. All that’s required is a bit of algebra, and some degree of patience on your part. That’s all.

The formula relates to a numerical series called Sums of Powers which pop up regularly in science and engineering. So it isn’t just eye candy; sum of power series have real practical value.

Let’s begin.

The simplest example of a sum of power series is the following:

\displaystyle T_{n} = 1+2+3+...+...+ n

where T_n denotes the sum of the first n terms which are all natural numbers (i.e., positive whole numbers or integers). To compute T_n , you can manually add up the first n terms in the expression, which is tedious and uncool. Alternatively, you could get it in one second by using the following nifty formula:

\displaystyle T_{n} = \frac{n(n+1)}{2}

The next power of sum series is one where the nth term (now denoted by R_n ) is obtained by adding up the squares of consecutive integers.

\displaystyle R_{n} = 1+4+9+16+....+n^2

Again, there is a neat formula for this sum:

\displaystyle R_{n} = \frac{2n^3 + 3n^2 + n}{6}

To see how useful this formula is, suppose you want to compute the value of

1^2 + 2^2 + 3^2 + 4^2 + ... + 9999^2 + 10000^2

You could do that by adding 10000 terms which is boring and tedious, or you could use the formula for R_n .

\displaystyle R_{10000} = \frac{2 \cdot 10000^3 + 3 \cdot 10000^2 + 10000}{6} = 333,383,335,000

Where did this wonderful formula come from? To find out, we will run through some algebra. The derivation will also point the way to a more general formula – one that allows us to compute the nth term of a power of sums involving any integer. Here goes.

Derivation of \bold R_{n}

Recall, R_n = 1^2 + 2^2 + 3^2 + 4^2 + ... + n^2

For reasons that will become apparent in a moment, we will look at the following telescoping sum involving cubes:

(n+1)^3 = 1^3 + (2^3 - 1) + (3^3 - 2^3) + ... + ((n+1)^3 -n^3)

Using summation notation, we can write this as

\displaystyle (n+1)^3 = 1 + \displaystyle\sum_{i=1}^{n} ((i+1)^3 - i^3)

Next, expand the expression (i+1)^3 using the binomial formula:

\displaystyle (i+1)^3 = i^3 + 3i^2 + 3i +1

and substitute this into the telescoping sum to get

(n+1)^3 = 1 + \displaystyle\sum_{i=1}^{n} (3i^2 + 3i+1)

Now we split the sum into three pieces and add each piece individually.

(n+1)^3 = 1+ 3 \displaystyle\sum_{i=1}^{n} i^2 + 3 \displaystyle\sum_{i=1}^{n} i + \displaystyle\sum_{i=1}^{n} 1

= 1 + 3 R_{n} +3 T_{n} + n

But we already know that T_n = \sum_{i=1}^{n} i is equal to \frac{(n^2+n)}{2} , so we can solve for R_{n} :

\displaystyle R_{n} = \frac{(n+1)^3 - n - 1}{3} - T_{n}

= \displaystyle \frac{n^3 + 3n^2 + 2n}{3} - \frac{n^2 + n}{2}

= \displaystyle \frac{2n^3 + 3n^2 + n}{6}

That was a lot of algebra, but the reward is the beautiful formula

\displaystyle 1^2 + 2^2 + 3^2 + 4^2 + ... + n^2 = \frac{2n^3 + 2n^2 + n}{6} = R_{n}

The General Formula

The next problem we are going to tackle is to derive a formula similar in spirit to R_n but where the series involve adding sums of kth powers for general k \geq 0 . Note: if you want to skip the derivations below, that’s fine. Just head over to the last section under “Theorem” and admire the general formula.

I will use \displaystyle F_{k} (n) to denote the general series we are interested in. We write

F_{k} (n) = 1^k + 2^k + 3^k + ... + n^k

We bring in the telescoping sum method that worked so well earlier and write

(n+1)^k = 1^k + (2^k - 1^k) + (3^k - 2^k) + ... + ((n+1)^k - n^k) ,

which, using summation notation, becomes

(n+1)^k = 1 + \displaystyle\sum_{i=1}^{n} ((i+1)^k - i^k)

As before, we expand (i+1) using the binomial formula to get

(i+1)^k = \displaystyle\sum _{j=0}^{k} {k \choose j} i^j

The last term (the j=k term) is i^k , so it cancels the i^k in the telescoping sum, leaving

(n+1)^k = 1 + \displaystyle\sum_{i=1}^{n}\sum_{j=0}^{k-1} {k \choose j} i^j

Now switch the order of the two sums, and lo and behold, we find the power sums F_0(n), F_1(n),..., F_{k-1}(n) appearing

(n+1)^k = 1 + \displaystyle\sum_{j=0}^{k-1} {k \choose j} \displaystyle\sum_{i=1}^{n} i^j = 1 + \displaystyle\sum_{j=0}^{k-1} {k \choose j} F_j(n).

You may ask, what good is a formula like this, which involves all sorts of quantities that we don’t know? The answer is that it relates each of F_0(n), F_1(n),..., F_{k-1}(n) .... with the previous ones.

To make this clear, we pull off the last term in the sum, i.e., the term with j=k-1 , and move all the other terms to the other side. We now have

\displaystyle {k \choose k-1} F_{k-1} (n) = (n+1)^k - 1 - \displaystyle\sum_{j=0}^{k-2} {{k \choose j} F_j(n)}

Now, {k \choose k-1} = k , so dividing by k gives the recursive formula

\displaystyle F_{k-1}(n) = \frac{(n+1)^k -1}{k} - \frac{1}{k} \displaystyle\sum_{j=0}^{k-2} {k \choose j} F_j(n)

We call this a recursive formula for the F_k ‘s because it expresses each F_k in terms of the previous ones. Let’s use the recursive formula to find a new power sum formula. Taking k = 4 in the recursive formula gives

\displaystyle F_3 (n) = \frac{(n+1)^4 -1}{4} - \frac{1}{4} \displaystyle\sum_{j=0}^{2} {4 \choose j} F_j(n)

= \displaystyle \frac{(n+1)^4 -1}{4} - \frac{1}{4} \bigg\{ {4 \choose 0} F_0(n) + {4 \choose 1} F_1(n) + {4 \choose 2} F_2(n) \bigg\}

We already know from earlier that

\displaystyle F_1(n) = T_n = \frac{n^2 +n}{2} and \displaystyle F_2(n) = R_n = \frac{2n^3 + 3n^2 + n}{6}

while the value of F_0 (n) = 1^0 + 2^0 + 3^0 + ... + n^0 = n.

Substituting these values into F_3(n) yields

\displaystyle F_3(n) = \frac{(n+1)^4 -1}{4} - \frac{1}{4} \bigg\{ {4 \choose 0} F_0(n) + {4 \choose 1} F_1(n) + {4 \choose 2} F_2(n) \bigg\}

= \displaystyle \frac{n^4 + 4n^3 + 6n^2 + 4n + 1 -1}{4} - \frac{1}{4} \bigg\{ n + 4 \frac{n^2+n}{2} + 6 \frac{2n^3 + 3n^2 + n}{6} \bigg\}

= \displaystyle \frac{n^4 + 2n^3 + n^2}{4}

Thus

\displaystyle F_3(n) = 1^3 + 2^3 + 3^3 + ... + n^3 = \frac{n^4 + 2n^3 + n^2}{4}

For example,

\displaystyle 1^3 + 2^3 + 3^3 + 4^3 + ... + 10000^3 = \frac{10000^4 + 2 \cdot 10000^3 + 10000^2}{4}

= 2,500,500,025,000,000.

Huge numbers arising from sums of high powers is the reason why recursive formulas for calculating them are so powerful.

Its time to summarize everything we’ve done in the form of a theorem:

Sum of Powers Theorem Let k \geq 0 be an integer. There is a polynomial F_k(n) of degree k+1 such that \displaystyle F_k(n) = 1^k + 2^k + 3^k + ... + n^k for every value of n = 1,2,3,... . These polynomials can be computed using the recursive formula

\displaystyle F_{k-1}(n) = \frac{(n+1)^k -1}{k} - \frac{1}{k} \displaystyle\sum_{j=0}^{k-2} {k \choose j} F_j(n)

Reference to the polynomial comes from the fact that each successive power sum is simply the polynomial term \frac{n+1)^k -1}{k} added to some multiples of the previous power sums. Special cases of this formula, for the low powers of k = 0, 1, 2, 3, and 4, were given earlier.

Leave a Reply