14
$\begingroup$

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 
  • 0
    @DKhanh: Yes; sorry about that. $M$ust have been the hour.2011-08-23

5 Answers 5

23

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.

14

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.

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.

6

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

[Note – this answer applied to an early version of the question, before it was edited.]

  • 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?2011-08-23
3

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$.

2

(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)$.