proof of all positive integers are polite numbers except powers of two

Theorem. All positive integers are polite numbers (that is, can be expressed as the sum of consecutive nonnegative integers in at least one way), with the exception of the powers of two.

Proof. Let k be a positive integer.

Let $k=2^h$ for $h>0$. Let’s suppose that $k$ is a polite number. We can write

$$k=\sum _{i=a}^{b}i$$

with $b>a$ and $a>-1$.

Then,

$$k=2^h=\sum _{i=a}^{b}i=\sum _{j=0}^{b-a}(j+a)=\sum _{j=0}^{b-a}j+\sum _{j=0}^{b-a}a=\frac{(b-a)(b-a+1)}{2}+(b-a+1)a$$

Multiplying both sides by two,

$$2^{h+1}=(b-a)(b-a+1)+2a(b-a+1)=(b-a+1)(b-a-2a)$$

If $b-a$ is even, then $b-a+1$ is odd and then $2^{h+1}$ would have an odd factor, contradiction. If $b-a$ is odd, then $b-a-2a$ is odd and then $2^{h+1}$ would have an odd factor, contradiction. Then, $k$ is not a polite number.

If $k=1$, then $k$ is a polite number trivially.

Now, suppose that $k>1$ is not a power of two. Then we can factor $k$ as $ah$ with $h=2b+1>1$ odd, $a>0$. Then,

$$\sum _{i=a-b}^{a+b}i=\sum _{j=-b}^b(j+a)=\sum _{j=-b}^{b}j+\sum _{j=-b}^{b}a=0+(2b+1)a=k$$

If $a-b\ge 0$ then $k$ is clearly a polite number.

If then

$$k=\sum _{i=a-b}^{a+b}i=\sum _{i=a-b}^{0}i+\sum _{i=1}^{|a-b|}i+\sum _{|a-b|+1}^{a+b}i=\sum _{|a-b|+1}^{a+b}i$$

so $k$ is a polite number.

Title	proof of all positive integers are polite numbers except powers of two
Canonical name	ProofOfAllPositiveIntegersArePoliteNumbersExceptPowersOfTwo
Date of creation	2013-03-22 18:42:47
Last modified on	2013-03-22 18:42:47
Owner	n847530 (22696)
Last modified by	n847530 (22696)
Numerical id	8
Author	n847530 (22696)
Entry type	Proof
Classification	msc 11A25