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=2h for h>0. Let’s suppose that k is a polite number. We can write

k=i=abi

with b>a and a>-1.

Then,

k=2h=i=abi=j=0b-a(j+a)=j=0b-aj+j=0b-aa=(b-a)(b-a+1)2+(b-a+1)a

Multiplying both sides by two,

2h+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 2h+1 would have an odd factor, contradictionMathworldPlanetmathPlanetmath. If b-a is odd, then b-a-2a is odd and then 2h+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,

i=a-ba+bi=j=-bb(j+a)=j=-bbj+j=-bba=0+(2b+1)a=k

If a-b0 then k is clearly a polite number.

If a-b<0 then

k=i=a-ba+bi=i=a-b0i+i=1|a-b|i+|a-b|+1a+bi=|a-b|+1a+bi

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