# 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 |