Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How do I prove that any even integer $n \neq 2^k$ is expressible as a sum of positive consecutive integers (more than 2 positive consecutive integer)?
For example:

14 = 2 + 3 + 4 + 5
84 = 9 + 10 + ... + 15

n = sum (k + k+1 + k+2 + ...) 
n ≠ 2^k
share|improve this question
2  
Positive integers? –  Arturo Magidin Aug 23 '11 at 4:46
    
Sorry man for my mistake, I has edited my question. –  DKhanh Aug 23 '11 at 5:03
    
Strictly more than $2$? Or $2$ or more? –  Arturo Magidin Aug 23 '11 at 5:17
1  
of course more than 2, if 2, it's not a even number –  DKhanh Aug 23 '11 at 5:36
1  
@J.M. Sum of 2 numbers, not the number 2. –  anon Aug 23 '11 at 5:47
show 2 more comments

5 Answers

up vote 18 down vote accepted

The sum of the integers from $1$ to $n$ is $n(n+1)/2$. The sum of the integers from $k$ to $k+n$ is then $$\begin{align*} k+(k+1)+\cdots+(k+n) &= (n+1)k + 1+\cdots+n\\ & = (n+1)k + \frac{n(n+1)}{2} \\ &= \frac{(n+1)(2k+n)}{2}.\end{align*}$$

Therefore, $a$ can be expressed as the sum of consecutive integers if and only if $2a$ can be factored as $(n+1)(2k+n)$.

Suppose that $a$ is a power of $2$. Then $2a$ is a power of $2$, so $(n+1)(2k+n)$ must be a power of $2$. If we want to avoid negatives, and also avoid the trivial expression as a sum with one summand, we must have $n\geq 1$ and $k\gt 0$. But the parities of $n+1$ and of $2k+n$ are opposite, so this product cannot be a power of $2$ unless either $n+1=1$ (which requies $n=0$) or $2k+n=1$ (which requires $k=0$). Thus, no power of $2$ can be expressed as a sum of at least two consecutive positive integers. In particular, $8$, $16$, $32$, etc cannot be so expressed.

On the other hand, suppose that $a$ is even but not a power of $2$. If we can write $2a = pq$ with $p\gt 1$ and odd, $q$ even, and $q\geq p+1$, then setting $n=p-1$ and $k=(q-p+1)/2$ gives the desired decomposition. If this cannot be done, then every time we factor $2a$ as $pq$ with $p\gt 1$ odd, we have $q\lt p+1$. Then we can set $n=q-1$ and $k = (p+1-q)/2$.

Thus, the powers of $2$ are the only even numbers that are not expressible as the sum of at least two consecutive positive integers.

Added. The OP has now excluded powers of $2$, but has also required that the sum contains strictly more than two summands; i.e., $k\gt 0$ and $n\gt 1$. With the above decompositions, the only case in which we could have $n=1$ is if $2a=pq$ with $p$ odd, $p\gt 1$, and $q=2$. But this is impossible, since $a$ is assumed to be even, and this leads to $2a = 2p$ with $p$ odd.

share|improve this answer
add comment

The argument of @Arturo Magidin that powers of $2$ are not representable can be extended to a "formula" for the number of representations of any positive integer. For no good reason, we use slightly different notation.

Let $w$ be a positive integer. We look for integers $m\ge 0$, $n>m$ such that $$w=(1+2+\cdots +n)-(1+2+\cdots +m).$$ With a little manipulation, we can rewrite this as $$2w=(n-m)(n+m+1).$$ Temporarily, we allow $n-m=1$, even though this corresponds to expressing $w$ as the "sum" of one integer.

The numbers $n-m$ and $n+m+1$ are of opposite parity and have product $2w$. Note also that $n-m<n+m+1$.

Now take any two numbers $x$, $y$ of opposite parity whose product is $2w$. Set $n-m=x$ and $n+m+1=y$. We can solve for $n$ and $m$, and obtain a representation of $w$ as a sum of consecutive integers (again, possibly only one such integer.)

We obtain such $x$, $y$ of opposite parity as follows. Let $2w=2^k q$ where $q$ is odd. Express $q$ as a product of two positive integers $u$ and $v$, not necessarily distinct. Multiply one of $u$ or $v$ (say $v$) by $2^k$, and let $x$ be the smaller of $u$ and $2^k v$, and $y$ the larger.

So the number of representations of $w$ as a sum of consecutive positive integers is $d(q)$, the number of divisors of $q$. If we do not want to allow the trivial representation of $w$ as the short sum $w$, the number of representations is $d(q)-1$.

If $w$ is a power of $2$, then $q=1$, and therefore there are no representations. If $$w=2^{a_0}p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k},$$ where the $p_1,p_2,\dots,p_k$ are distinct odd primes, then the number of non-trivial representations is $$(a_1+1)(a_2+1)\cdots(a_k+1)-1.$$
In particular, if $w$ is not a power of $2$, there is at least one non-trivial representation.

Added: The OP has now excluded the possibility of $2$ consecutive integers. Since the original question is about even $w$, that makes no difference. For odd $w$, we just remove $1$ of the representations counted above.

share|improve this answer
add comment

8?${}{}{}{}{}{}{}{}{}{}{}{}{}$

share|improve this answer
3  
$10 = 1 + 2 + 3 + 4$, $12 = 3 + 4 + 5$ –  Jon Aug 23 '11 at 4:28
2  
For fun, $8=(-7)+(-6)+\cdots+7+8$. But positive integers is (are?) more interesting. Need also to specify how many consecutive integers. One? More than one? –  André Nicolas Aug 23 '11 at 4:41
add comment

Idea: First find a sum divisible by a correct power of two, say, $2^\ell$. That is a solution modulo $2^{\ell+1}$. Then fix that solution within its coset.

=================

Let $m=2^\ell t$ with $t>1$ an odd number. Then the sum of consecutive integers $$0+1+\cdots+(2^{\ell+1}-1)=2^{\ell}(2^{\ell+1}-1)$$ has $2^{\ell+1}$ terms. Here $t+1-2^{\ell+1}$ is an even number, call it $2k$. If $k\ge0$, then we can just add $k$ to all the $2^{\ell+1}$ terms in the above sum, and we have found a solution.

OTOH if $k<0$, then we need to subtract $|k|$ from all those terms to get the correct sum. When we do that we introduce some negative numbers. Those will get cancelled by their positive counterparts. Because $t>1$, there will be more than one number remaining. This is because after subtracting $|k|$ from all the terms, the largest term $L$ is $L=2^{\ell+1}-1-|k|$ and the smallest term $S$ is $S=k<0$. The non-cancelled numbers are $|S|+1,|S|+2,\ldots,L$, so there are $$L-|S|=L+S=2^{\ell+1}-1-2|k|=2^{\ell+1}-1+2k=t$$ of them. As $t>1$ we again have a non-trivial presentation of $m$ as a sum of positive consecutive integers.

Example: $m=12$ gives $\ell=2,t=3$. Initially use the sum $0+1+2+\cdots+7=28$ with 8 terms. The sum is too large by 16, so to fix that we need to subtract $2$ from all the terms, and we end up with $(-2)+(-1)+0+1+2+3+4+5=3+4+5$.

share|improve this answer
add comment

(The following is merely a simplification of @Arturo Magidin's proof. So, please do not upvote my post.) Suppose $S=k+(k+1)+\ldots+\left(k+(n-1)\right)$ for some $k\ge1$ and $n\ge2$. Then $$ S = nk + \sum_{j=0}^{n-1} j = nk+\frac{n(n-1)}{2} = \frac{n(n+2k-1)}{2}. $$ Hence $S\in\mathbb{N}$ can be written as a consecutive sum of integers if and only if $2S = nN$ with $N\ (=n+2k-1) >n\ge2$ and $N, n$ are of different parities.

If $S$ is a power of $2$, so is $2S$. Hence the above factorization cannot be done.

If $S$ is not a power of $2$ (whether it is even is immaterial), we may write $2S=ab$, where $a\ge3$ is odd and $b\ge2$ is a power of $2$. Therefore we can put $N=\max(a,b)$ and $n=\min(a,b)$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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