The sum of the first n positive integers

In this article, I’ll illustrate how we can use two different strategies to develop the same formula. This relates to the toothpick problem we explored in class.

Strategy 1

There’s a story, probably apocryphal, about the great mathematician Carl Friedrich Gauss as a young man. He was told to add the numbers 1 to 100, which he did in less than a minute. He observed that \(1 + 100 = 101\), \(2 + 99 = 101\), and so on up to \(50 + 51 = 101\). Since there were 50 equations that each added to 101, the total sum must be 5050.

We can generalize this technique to quickly add any number of positive integers. Let’s call the highest integer \(n\), and the sum \(s_n\). The sum of each pair will be \(n + 1\). If \(n\) is even, then there will be \(\frac{n}{2}\) pairs, so the sum of all values will be \[\frac{n(n+1)}{2}\]

If \(n\) is odd, the situation is a little trickier. There will be \(\frac{n-1}{2}\) pairs and a loner in the middle, of \(\frac{n + 1}{2}\). For instance, for the first nine positive integers, the pairs are \(1 + 9\), \(2 + 8\), \(3 + 7\), and \(4 + 6\), and the loner is \(\frac{9+1}{2} = 5\). To find the sum, multiply the highest integer by the number of pairs, then add in the loner: \[\frac{(n+1)(n-1)}{2} + \frac{n + 1}{2} = \frac{(n+1)(n – 1) + n + 1}{2}\] This looks daunting, but we can simplify it: \[\frac{(n+1)(n-1) + (n+1)(1)}{2} = \frac{(n+1)(n-1+1)}{2} \\ = \frac{(n+1)n}{2} \\ = \frac{n(n+1)}{2}\] This is the same formula we got when \(n\) is even, so we can use it for all cases.

This is the standard way of developing the formula \[s_n = \frac{n(n+1)}{2}\]

Strategy 2

Let’s look at a different route, one based on the pattern of the sums. Here are the first six sums:

  • \(s_1 = 1\)
  • \(s_2 = 1 + 2 = 3\)
  • \(s_3 = 1 + 2 + 3 = 6\)
  • \(s_4 = 1 + 2 + 3 + 4 = 10\)
  • \(s_5 = 1 + 2 + 3 + 4 + 5 = 15\)
  • \(s_6 = 1 + 2 + 3 + 4 + 5 + 6 = 21\)

Here are means of each, \(m_n\). Recall: To find the mean, divide the sum by the number of values.

  • \(m_1 = 1\)
  • \(m_2 = 3/2 = 1.5\)
  • \(m_3 = 6/3 = 2\)
  • \(m_4 = 10/4 = 2.5\)
  • \(m_5 = 15/5 = 3\)
  • \(m_6 = 21/6 = 3.5\)

The pattern is obvious: When the value goes up by 1, the mean goes up by 0.5. If we double the means, we get {2, 3, 4, 5, 6, 7}, which is always one more than \(n\). From this pattern, we predict that \(m_n = \frac{n+1}{2}\).

Since the mean is equal to the sum divided by the number of values, i.e., \(m_n = \frac{s_n}{n}\), this means \(\frac{s_n}{n} = \frac{n+1}{2}\). Multiply through by \(n\) to get \[s_n = \frac{n(n+1)}{2}\] which is the same formula we developed above.

Inductive Proof (Bonus)

To be mathematically rigorous, it’s not enough to say that we found a pattern, and so that pattern must always hold. It’s possible that the mean follows that pattern for a while, and then something happens at, say, \(m_9\) or \(m_{100}\) to break it.

To account for this possibility, mathematicians developed what is called an inductive proof. Such a proof consists of two parts:

  • Show that a formula holds for some simple case, such as \(m_1\).
  • Show that if a formula holds for a certain value (\(m_{k-1}\)), it holds for the next value as well (\(m_k\)).

If it always holds for the first case and for each case after the first case, then it holds for all cases.

We already know that \(m_1 = \frac{n + 1}{2}\), since that’s part of how we got the formula in the first place. We would need to show that, if \[m_{k-1} = \frac{k – 1 + 1}{2} = \frac{k}{2}\] then \[m_k = \frac{k+1}{2}\]

Let’s say we have the mean of a set of numbers. We’re going to add a new number to the set and find the new mean. Since the mean of a set of numbers is the sum divided by the count, that is, \(m = \frac{s}{n}\), the sum of the values is the mean times the count (i.e., \(s = mn\)). The new sum, including the new value \(j\), is \(s + j\). The new mean is \(\frac{s + j}{n + 1}\).

In this case, \(s_{k-1} = (k-1) m_{k-1}\), \(n = k – 1\), and \(j = k\). So the new sum is \[s_k = (k-1) m_{k-1} + k\] and the new mean is \[m_k = \frac{s_k}{k} = \frac{(k-1) m_{k-1} + k}{k}\] We want to know the value of \(m_k\) when \(m_{k-1} = \frac{k}{2}\), so we substitute appropriately, then simplify: \[m_k =  \frac{(k-1)\frac{k}{2} + k}{k} \\ = \frac{(k-1)k + 2k}{2k} \\ = \frac{(k-1+2)k}{2k} \\ = \frac{k+1}{2}\]

This is what we needed to demonstrate, so our proof is complete: Since \(m_1 = \frac{1 + 1}{2} = 1\) and \(m_{k-1} = \frac{k}{2} \Rightarrow m_k = \frac{k+1}{2}\), we know that the pattern we established for the mean of the sum of consecutive positive integers always holds up.

Since that pattern holds up, we can also conclude that the formula we developed for the sum also holds up.

Leave a Reply

Your email address will not be published. Required fields are marked *