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?

  • $\begingroup$ We could consider that $2^2$ is the sum of the set of consecutive natural numbers {4}. Presumably you mean it cannot be the sum of more than one consective natural number? $\endgroup$ – Ronald Apr 1 '12 at 12:21
  • $\begingroup$ @ronald: yes, sum of more than one, that's what I mean. $\endgroup$ – Keneth Adrian Apr 1 '12 at 12:25
  • $\begingroup$ There is a proof for the conjecture "A natural number is a sum of consecutive integers if and only if it is not a power of 2." that can be found at: www.csudh.edu/math/wpong/_downloads/sci.pdf $\endgroup$ – NoChance Apr 1 '12 at 14:03
  • $\begingroup$ See also this related thread: Prove that all even integers $n \neq 2^k$ are expressible as a sum of consecutive positive integers $\endgroup$ – t.b. Apr 4 '12 at 18:30

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.

| cite | improve this answer | |

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.


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 -

| cite | improve this answer | |
  • $\begingroup$ Whoa... Neat stuff. Maximum respect Sir +1 $\endgroup$ – funktor Apr 1 '12 at 12:22
  • 13
    $\begingroup$ Isn't it odd then that $1+2+3+4$ is even? $\endgroup$ – André Nicolas Apr 1 '12 at 13:42
  • 3
    $\begingroup$ I think what @AndréNicolas is saying is that a nontrivial sum of consecutive natural numbers can be even with an even number of terms. It's a little surprising that this answer has so many upvotes for being so incomplete. $\endgroup$ – Antonio Vargas Apr 1 '12 at 15:59
  • 1
    $\begingroup$ Of course the idea of mixedmath can be made to work just fine. In the other case (a sum of an even number of consecutive integers), the midpoint is half of an odd integer, $\dots$. $\endgroup$ – André Nicolas Apr 1 '12 at 16:29
  • $\begingroup$ @Andre: Thank you for that - I missed a big point there. $\endgroup$ – davidlowryduda Apr 1 '12 at 16:43

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.

| cite | improve this answer | |

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

| cite | improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.