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
    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?2012-04-01
  • 0
    @ronald: yes, sum of more than one, that's what I mean.2012-04-01
  • 0
    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.pdf2012-04-01
  • 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
    Whoa... Neat stuff. Maximum respect Sir +12012-04-01
  • 13
    Isn't it odd then that $1+2+3+4$ is even?2012-04-01
  • 3
    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.2012-04-01
  • 1
    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$.2012-04-01
  • 0
    @Andre: Thank you for that - I missed a big point there.2012-04-01
  • 0
    @Antonio: Whoops! I was typing hurriedly and missed a big point. Thank you for pointing that out to me2012-04-01
  • 0
    mixed, are 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.