Polite numbers

This lesson can be given as part of a lesson on proof by cases.

Here is 15 as a 5-step, 3-step, and 2-step number (from left to right):

Find a simple rule to determine if a number is a 2-step number. Find a simple rule to determine if a number is a 3-step number. Can you find rules for any number of steps? Given a particular number, can you find the number of ways in which it can be written as a step number? We saw that 15 was a 2-step, 3-step, and 5-step number. Find three other numbers that are also 2-step, 3-step, and 5-step numbers.

Step numbers are more commonly referred to as polite numbers. A polite number is a whole number that can be represented as the sum of two or more consecutive positive whole numbers. For example, 4 + 5 is a polite number, but 1 is not a polite number, because there are no two consecutive positive whole numbers that add up to 1.

If a polite number starts with \(1,\) such as \(1 + 2 + 3,\) then it's also a triangular number. Otherwise, it's the difference of two nonconsecutive triangular numbers. For example,

$$3 + 4 + 5 = 1 + 2 + 3 + 4 + 5 - 1 + 2.$$

In general,

$$i + (i + 1) + (i + 2) + \ldots + j = T_j - T_{i - 1}.$$

Theorem: A number is polite if and only if it is not a power of 2.


Proof 1:

Numbers of the form \(2^n\) have no odd factors other than 1.

Consider the consecutive numbers, \(a,\) \((a + 1),\) \((a + 2),\) \(\ldots,\) \((a + k),\) with \(a \ge 1,\) and \(k \ge 1.\)

Write down the sum of the numbers in ascending order:

$$S = a + (a + 1) + (a + 2) + \ldots + (a + k)$$

Write down the sum of the numbers in descending order:

$$S = (a + k) + (a + k - 1) + \ldots + (a + 1) + a$$

Write the sequences above each other, so the terms line up, then add corresponding terms.

$$2S = \underbrace{(2a + k) + (2a + k) + \ldots + (2a + k)}_{k + 1\text{ times}}$$

There are \(k + 1\) terms in \(2S,\) each of which is equal to \((2a + k).\) Therefore, \(2S = (k + 1)(2a + k).\) Therefore,

$$S = \dfrac{(k + 1)(2a + k)}{2}$$

If \(k\) is odd, then \(2a + k\) is odd, and thus, the sum has an odd factor of \((2a + k).\) Since \(a \ge 1,\) and \(k \ge 1,\) we have \(2a + k \gt 1.\)

If \(k\) is even, then \(k + 1\) is odd, and thus, the sum has an odd factor of \(k + 1.\) Since \(k \ge 1,\) we have \(k + 1 \gt 1.\)

Therefore, in every case the sum of the consecutive numbers has an odd factor which is greater than 1. Since any sum of consecutive numbers must have an odd factor greater than 1, it cannot be of the form \(2^n.\)


Proof 2:

Take \(n\) consecutive numbers, where \(n \gt 1.\)

If their total is a power of 2, then all the factors of the total, other than 1, will be even.

The sum of the numbers is equal to the mean of the numbers, multiplied by \(n.\)

Since the numbers are evenly spread out, the mean is equal to the median.

If \(n\) is odd, then the median will be the same as the middle number, \(m.\)

The total will be \(n \cdot m,\) which has the odd factor \(n.\)

Therefore, if \(n\) is odd, the total has an odd factor greater than 1, and thus, cannot be a power of 2.

If \(n\) is even, then the median will be the average of the two middle numbers, which we'll call \(a\) and \(b.\) So the median is \((1/2)(a + b).\)

The total is \((n / 2)(a + b),\) and so \(a + b\) is a factor.

Since \(a\) and \(b\) are consecutive, we know \(a + b\) is odd, and thus, the total has an odd factor.

Therefore, if \(n\) is even, the total has an odd factor greater than 1, and thus, cannot be a power of 2.

Therefore, the total of \(n\) consecutive numbers has an odd factor greater than 1, for both odd and even values of \(n,\) and so it can never be a power of 2.


Proof 3:

Numbers of the form \(2^n\) have no odd factors other than 1.

The sum of the consecutive numbers \(m + 1,\) \(m + 2,\) \(\ldots,\) \(n,\) is the same as the difference between the \(m\)th and \(n\)th triangular numbers.

The \(n\)th triangular number is equal to \((1/2)n(n + 1).\)

We can write the difference between the \(m\)th and \(n\)th triangular numbers as

$$\dfrac{1}{2}n(n + 1) - \dfrac{1}{2}m(m + 1),$$

where \(n \ge 1,\) \(m \ge 1,\) and \(n \gt m + 1.\)

Factoring gives us

$$\dfrac{1}{2}[n(n + 1) - m(m + 1)].$$

This is equal to

$$\dfrac{1}{2}\left(n^2 + n - m^2 - m\right)$$

Substituting \(n = m,\) into the previous expression, gives 0. Thus, \((n - m) is a factor. Factoring gives us

$$\dfrac{1}{2}(n - m)(n + m + 1).$$

If \(n\) and \(m\) are both odd, or both even, then \(n + m + 1\) is odd. Since \(n,\,m \ge 1,\) we know that \(n + m + 1 \gt 1.\)

If one of \(n,\,m\) is odd, and the other is even, then \(n - m\) is odd. We know \(n \gt m + 1,\) so we have \(n - m \gt 1.\)

Therefore, the expression

$$\dfrac{1}{2}(n - m)(n + m + 1),$$

always has an odd factor which is greater than 1.

Since any sum of consecutive numbers must have an odd factor greater than 1, it cannot be of the form \(2^n.\)


Sources: Polite Numbers and Impossible Sums by NRICH.