Formula for the sum of the integers from m to n, with Proof!

So I’m reading some math for pleasure (and for some scripting ideas) and I arrive at the following problem:

Find a formula for the sum of the natural numbers from m to n.

In the chapter they discuss and derive the formula for the sum of the integers from 1 to n. This can be stated as

(1)   \begin{equation*} \sum_{k=1}^{n} k = 1 + 2 + \ldots + n = \frac{n(n+1)}{2} \end{equation*}

The solution then is relatively straightforward, just subtract the first m – 1 integers from equation (1). That is, the sum from 1 to the m – 1 natural numbers is given by

(2)   \begin{equation*} \sum_{k=1}^{m-1} k = \frac{(m-1)(m)}{2} \end{equation*}

Subtracting (2) from (1) gives

(3)   \begin{equation*} \sum_{k=m}^{n} k = \frac{1}{2} [n(n + 1) - (m - 1)m] \end{equation*}

Note that m and n are natural numbers, and that m ≤ n.

Programmatically speaking, it would be nice if when I divided by 2, I always got an integer. Logically, this should be the case since I’m just adding together natural numbers and they should sum to an natural number. However, I thought it might be a nice exercise to write out a proof of this fact.

Preliminaries

First, a quick preliminary (which I won’t prove). Note that any even integer multiplied by any odd integer always results in an even integer. The the proof follows from the fact that since an even integer is divisible by 2, the product of an even and odd integer is still divisible by 2 and thus also even.

Note then that (m - 1)m is the product of an even integer times an odd integer. Similarly for n(n + 1). This result extends to natural numbers since the natural numbers are a subset of the integers.

Here is a quick example. Pick m = 5. Then m - 1 = 4 and so (m - 1)m = 4 \times 5 = 20. In other words if m is odd then m - 1 is even. Conversely, if m is even then m - 1 is odd. A similar situation occurs with n and n + 1.

The proof

Suppose that m and n are natural numbers and that m \le n. Consider the expression n(n + 1) - (m - 1)m. Note that both (m - 1)m and n(n + 1) are always even since they are always the product of and even number and odd number for any choice of m, n \in \mathbb{N}. Since 2 \hspace{1 mm} \vert \hspace{1 mm} (m - 1)m and 2 \hspace{1 mm} \vert \hspace{1 mm} n(n + 1) this means 2 \hspace{1 mm} \vert \hspace{1 mm} [(m - 1)m + n(n + 1)]. Therefore the expression (m - 1)m + n(n + 1) is always an even natural number and further

(4)   \begin{equation*} \frac{1}{2} [(m-1)m + n(n+1)] \in \mathbb{N} \end{equation*}

This completes the proof

At some point maybe I’ll write up a script to calculate the sum of the integers numbers from m to n.

Notes

If you’re not math symbol aware then I’ll point out that \mathbb{N} represents the set of natural numbers. These are the numbers 1, 2, 3, \ldots. So n \in \mathbb{N} means that n is an natrual number. The expression 2 \hspace{1 mm} \vert \hspace{1 mm} 4 says that “2 divides 4″. Another way to say this is 4 is divisible by 2.

Leave a Reply

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

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>