Wednesday, May 21, 2014

Daily 5: Summation Formulas

In class, we learned about the Indian mathematician Brahmagupta and his contributions to the field. In addition to his other writing in number theory, Brahmagupta determined formulas for the following summations:
• 1 + 2 + 3 + ...   (sum of a finite set of natural numbers),
• 1 + 4 + 9 + ...   (sum of a finite set of squares), and
• 1 + 8 + 27 + ... (sum of a finite set of cubes).
We will develop these formulas here, beginning with the sum of the integers 1 through n. Let's first make a table that will help us to determine a pattern.

n                               1        2        3        4        5        6
Sum of natural numbers, x(n)          1        3        6       10      15       21

Notice that for each term, the difference between the nth term and the (n - 1)th term is n. Of course, we could now easily write a recursive formula for the (n + 1)th term using this information, namely,

x(n + 1) = x(n) + n + 1.

That was too easy, and is only useful if we know both the current n and the value of x(n). Both of these things are bad. What we wish to find instead is a closed formula, one which works regardless of the information we are given. In this way, we can find a value for something like x(364) without having to calculate everything up to and including x(363). Because of this condition, we will want to find a formula that makes no mention of x(n). Rather, we must base it on the only other variable we have at our disposal: n.

At first glance we might try something like x(n) = 2n + 1, but we see that this fails immediately after the first term in the sequence. We are equally unsuccessful with other attempts like x(n) = 3n - 3 and we may begin to foam at the mouth. When all hope seems lost, we notice what happens when we multiply two consecutive values of n and compare them to the corresponding values of x(n). After hours of careful observation and calculation, we ascertain that the value of x(n) is half of the smaller of the two n values we chose. That is, the formula we want for the summation of the natural number sequence is

x(n) = .5(n)(n + 1).

With the closed formula for the sum of a finite set of natural numbers determined, we move now to the sum of a finite set of squares, as seen above. We once again begin with a table.

n                     1        2        3        4        5        6
Sum of squares, y(n)       1        5       14      30      55      91

Like before, we wish to find a closed formula for y(n) that is not dependent on values such as y(n - 1). So, as before, we want a formula that relies only on the variable n. We saw in the last case that multiplying n's together proved to be better than multiplying n with constants, so we will try this first. Of course, we will want a formula that yields larger values than x(n) does, so trying something like y(n) = .5(n)(n + 1)(n + 2) might be a decent place to start. Of course, we see that this doesn't work right away. It gives the wrong value of y(1) = 3, so we must look for something else. In general, we see that (n)(n + 1)(n + 2) is no multiple of n, and that no sort of useful pattern is found using this at all, so we will have to take a different approach implementing n in a different way. Like Lewis and Clark before us, we must leave behind the comfort of the known and familiar in our search for the new and exciting.

Now, we try (n)(n + 1)(2n + 1) instead and our mouths begin to salivate. Unlike our previous "base" formula, this attempt seems to give a multiple of our choice of n, at least for the first few values. After calculating several more values and once we become more convinced that the pattern really exists, we proclaim that this formula gives precisely 6 times the value of y(n). So, we conclude that the formula for the sum of squares is

y(n) = (1/6)(n)(n + 1)(2n + 1).

The final formula we want is for the sum of cubes, z(n), which we were to find in class. Of course, finding the formula is not possible without the following table.

n                     1         2         3         4         5         6
Sum of cubes, z(n)      1         9       36      100      225      441

"My word!", you may have said audibly upon seeing this table. If you did, you likely saw that each term in z(n) is a perfect square. The square root of each term will be incorporated in our formula for z(n), so we now focus our attention on them. They are

1   3   6   10   15   ...

How are these numbers related to n? The difference between the terms corresponding to n + 1 and n is certainly n but, as in the first case above, this will prove to be utterly useless for our quest. However, our result from the first case, x(n) = .5(n)(n + 1), will prove to be incredibly useful. In fact, we simply have to square this result to obtain the values we need for z(n). Thus, the formula for the sum of cubes is simply

z(n) = x(n)2
= [.5(n)(n + 1)]2

We have now found closed formulas for the sum of natural numbers, sum of squares, and sum of cubes. As discussed above, the closed forms of these formulas have the advantage of not relying on previous terms in the sequence; we merely need to choose a value for n, and the formula will give us the value of the nth term in the sequence. I tried to find a formula for the sum of the natural numbers to the fourth power, but I gave up rather quickly. I couldn't find anything about this topic on Google, but I didn't look very hard at it yet and might look into it more later.