5
$\begingroup$

Possible Duplicate: A proof that powers of two cannot be expressed as the sum of multiple consecutive positive integers that uses binary representations?

Suppose we have an arithmetic sequence $a_n= a_1 + (n-1)d$ such that $a_i \in \mathbb{N}$. If we let $d=1$, then we have consecutive natural numbers. Now, we are guaranteed that $\sum_{i=1}^{k}{a_i}= \lambda, \lambda \in \mathbb{N}$ Now, all elements of $\mathbb{N}$ are expressible into some $\sum_{i=1}^{k}{a_i}$ but it is not unique. Say $\lambda = 15 = 1+2+3+4+5= 7+8.$ But if $\lambda = 2^n $ $\forall$ $ n \in \mathbb{N}^* $, there is no $\sum_{i=1}^{k}{a_i}$ possible where $d=1$.

How can we show that all natural numbers of the form $2^n $ $\forall$ $ n \in \mathbb{N}^* $ cannot be written as sums of consecutive natural numbers?

  • 0
    See also this related thread: [Prove that all even integers $n \neq 2^k$ are expressible as a sum of consecutive positive integers](http://math.stackexchange.com/questions/59131/)2012-04-04

4 Answers 4

0

Hint: The powers of 2 are the only numbers that have no odd factors

13

There is a deceptively simple elementary-number-theoretic approach to this problem.

Suppose we have such a set of consecutive natural numbers. For a nontrivial sum of consecutive natural numbers to be even, there must an an odd number of terms. Suppose we have $k$ terms, with $k$ odd. Then there is a well-defined middle/median number. Call it $n$. Then we have that the sum of the $k$ numbers is $kn$.

You ask why $kn \not = 2^l$. But note that $k$ is odd.

Aha - so it can't happen.

EDIT

Ah yes - I disappeared for a bit, but Andre makes a very good point!

So, let's extend this so that it works:

It is not true that for a sum of consecutive numbers to be even, there must be an odd number of terms. There are two types of these sums: sums like $1 + 2 + 3$ and sums like $1 + 2 + 3 + 4$ (perhaps throwing the even number on the other side - that's not important). The former is considered above.

In the other case, when there are an even number ($k$) terms, then the median term is half of an odd integer ($n/2$). So then, if we claim that $kn/2 = 2^l$, we are also claiming that $kn = 2^{l+1}$, with the same contradiction as in the argument above.

Thank you Andre for pointing that out -

  • 0
    mixed, a$r$e you running for mod? You'd have my vote...2012-05-01
2

I will give numeric proof.

In addition to mixedmath's words.

We have: $\sum_{i=1}^{k}{a_i}$ And, of course, for $a_1 = n$ it's equal to: $n + (n+1) +\cdots + (n+(k-1)) = nk + (1+2+\cdots+(k-1)) = nk + \frac{k(k-1)}2 = \frac{k(2n + k - 1)}2$ Suppose, that $\exists s\in\mathbb{N}$: $ 2^s = \frac{k(2n+k-1)}2 $ Let's multiply both sides by two: $ 2^{s+1} = k(2n+k-1) $ So, $k$ can not be odd, because $2^{s+1}$ has only even dividers, but it also can not be even, because sum $(2n+k-1)$ would be odd. So, It's impossible.

2

The claim as stated is false. If we stipulate that the sequence has length greater than $1$ and all the terms are positive, then it is true.

Consider the identity $ \sum_{k=m}^n k=\frac12(n+m)(n-m+1)\tag{1} $ holds because the sum consists of $n-m+1$ numbers whose average is $\frac12(n+m)$.

Note that $(n+m)-(n-m+1)=2m-1$ is odd. Thus, one or the other of $n+m$ or $n-m+1$ must be odd.

Suppose the sum in $(1)$ is $2^j$. The only odd factor of $2^j$ is $1$, so either $n-m+1=1$ or $n+m=1$.

Case $\mathbf{1}$: $\mathbf{n-m+1=1}$

If $n-m+1=1$, then n=m and the sum is a singleton, $n$. If $n=2^j$ this contradicts the claim unless we stipulate a sequence has a length greater than $1$.

If the sequence has more than one term, then we cannot have Case $1$.

Case $\mathbf{2}$: $\mathbf{n+m=1}$

If $n+m=1$, then one of the terms must be less than $1$. Furthermore, the sum is then $\frac12(n-m+1)=n$ and again we contradict the claim if $n=2^j$. For this case we can have $ \begin{align} 1&=0+1\\ 2&=-1+0+1+2\\ 4&=-3+-2+-1+0+1+2+3+4 \end{align} $ as counterexamples.

If the sequence is all positive, then we cannot have Case $2$.

The problem as stated allows Case $1$, but not Case $2$. However, if the sequence has more than one term and is all positive, then the claim is true.