Prove that any number that is not a power of 2 can be expressed as a sum of two or more consecutive positive integers

Question

1) Prove that any number that is not a power of $2$ can be expressed as a sum of two or more consecutive positive integers, but that this is not possible for powers of $2$.

2) Which numbers can be expressed as a sum of two or more consecutive odd positive integers?

I have found many questions the first part but am unsure on how to solve the second part of the question. My guess is using $(n+1)(n+3)...$ and so on but am unsure how to use this.

Answer 1

Hint: For 2) you just write it as difference of two sums:

$$\sum_{i=0}^{n-1} (2i+1)-\sum_{i=0}^{m-2} (2i+1)$$,

where $m$ is the first integer and $n$ is the last integer ($n>m$).

Can you simplify it?

Answer 2

For the second, note that the sum of the odd numbers from $1$ to $2k+1$ is $(k+1)^2$. The numbers that can be written as a sequence of odd numbers are those that can be expressed as $(k+1)^2-(m+1)^2=(k+m+2)(k-m)$. You need to be able to factor the number into factors of the same parity.

Answer 3

HINT:

As I said in the comments for the first question look at: Which positive integers can NOT be written as a sum of consecutive positive integers

And for the second part here is a hint:

Adding up the first $m$ positive odd numbers is equal to $m^2$. $$ \circ \ \circ \\ \bullet\ \circ \\ $$ as $1+3=4$, further $$ \bullet\ \bullet\ \bullet\\ \circ \ \circ \ \bullet \\ \bullet\ \circ \ \bullet \\ $$ as $1+3+5=9$, and $$ \circ\ \circ\ \circ\ \circ\\ \bullet\ \bullet\ \bullet\ \circ\\ \circ \ \circ \ \bullet \ \circ\\ \bullet\ \circ \ \bullet \ \circ\\ $$ as $1+3+5+7=16$, and so on.

EDIT: I edited out the solution since this answer only wants to contain hints. If you still have troubles feel free to ask in the comments :)

Answer 4

1) if $M$ is not a power of two the $M$ has an odd divisor so $M = a*(2m+1)$ for some $m$ and some $a$ (which could be $1$, odd, even or a power of $2$... we don't care)

$2m + 1 = m + (m+1)$.

And $2m + 1 = (m-1) + (m + 2) = (m-2) + (m+3)= ... = (m-k) + (m+ k+1)$

So $\underbrace{\underbrace{(m-(a-1))\underbrace{(m-(a-2)...\underbrace{m(m+1)}_{=2m+1}....(m + (a-1))}_{=2m+1}(m+a)}_{=2m+1}}_{a\text{ times}}=$

$a(2m+1)$.

2) If there are an odd number, $2a + 1$ of terms and we let the $k$ be the middle term then we will have $(k-2a)+ (k-2a+2)+...... + (k-2) + k + (k+2) + .....+(k+2a) = (2a+1)k; k > 2a$ so any composite odd number is possible (if we let the middle term be one of the smaller factors.

And even number or an odd prime or a unitary number will not be possible the way.

If there are an even number, $2a$ of terms then there is no middle term. But there will be a middle pair $2k- 1$ and $2k + 1$ and the series will be $(2k -2a-1) + (2k -2(a-1) - 1) + ..... +(2k -2 -1)+ (2k-1)+ (2k+1) + (2k+2+2) + ...... + (2k +2(a-1) + 1) +(2k+2a + 1) = 2a*k$

The can be an even number with an odd factor so long as it has an odd factor larger an even factor. An even number is of the form $2^j*m$ where $m$ is odd. We require $m > 2^j$.

So.... odd composites, and even numbers where the odd factor is larger than the power of $2$ factor.

Answer 5

1. Assume $2^m;\ m\ge 2$ can be expressed as the sum of consecutive integers $n+1,n+2,\dots n+k$. Then it is the difference between the sum of the first $k$ integers and the sum of the first $n$ integers. $$2^m=\frac{k(k+1)}{2}-\frac{n(n+1)}{2}=\frac{k^2-n^2+k-n}{2}\Rightarrow 2^{m+1}=(k+n)(k-n)+(k-n)=(k+n+1)(k-n)$$ Now $(k+n)$ and $(k-n)$ have the same parity, so $(k+n+1)$ and $(k-n)$ must have different parity, i.e.one of them must be odd. But $2^{m+1}$ has no odd factors, so the assumption is false and $2^m$ cannot be expressed as the sum of consecutive integers.

Any odd number $2a+1$ can be expressed as the sum of two consecutive integers, $2a+1=a+(a+1)$

Any even number $b$ not a perfect power of two has at least one odd prime factor: $b=2^m\prod q_i$ where $q_i$ are odd primes, not necessarily distinct.

Case 1: $b$ contains more than one odd prime factor: $i\ge 2$. Let $q_1=\min(q_i); j=\frac{q_1-1}{2}$. Also, $s=\frac{b}{q_1}$. The consecutive integers $s-j, s-j+1,\dots s,\dots s+j-1,s+j$ sum to $b$ as the sequence contains $q_1$ integers of average value $s$, and $s\cdot q_1=b$. This approach will certainly work for the smallest odd prime factor of $b$, and may work for some larger odd prime factors of $b$ as well.

Case 2: $b=2^mq$. Then $b$ is the sum of $2^{m+1}$ consecutive integers: $$b=((\frac{q}{2}-\frac{2^{m+1}-1}{2})+(\frac{q}{2}-\frac{2^{m+1}-1}{2}+1)+\dots +(\frac{q}{2}-\frac{2^{m+1}-1}{2}+(2^{m+1}-1)))$$ Notice that each term features the difference between two half integers, and so results in an integer. This sequence contains $2^{m+1}$ integers with an average value of $$\frac{(\frac{q}{2}-\frac{2^{m+1}-1}{2})+(\frac{q}{2}-\frac{2^{m+1}-1}{2}+(2^{m+1}-1))}{2}=\frac{q}{2}$$ Thus the sum is $2^{m+1}\cdot \frac{q}{2}=2^mq=b$.

2. Any even number which is a multiple of $4$ can be expressed as the sum of two consecutive odd integers: $4a=(2a-1)+(2a+1)$.

Any odd composite number $b$ has at least two odd prime factor: $b=\prod q_i$ where $q_i$ are odd primes, not necessarily distinct, and $i\ge 2$. Let $q_1=\min(q_i); j=\frac{q_1-1}{2}$. Also, let $s=\frac{b}{q_1}$. Note that $s$ is odd. The consecutive odd integers $s-2j, s-2(j+1),\dots s,\dots s+2(j-1),s+2j$ sum to $b$ as the sequence contains $q_i$ integers of average value $s$, and $s\cdot q_1=b$.

If an odd prime number could be expressed as the sum of two or more consecutive odd integers, it would be equal to the number of such consecutive odd integers times their average value, which would be equal to the least plus the greatest divided by $2$. Note that the average of two odd numbers is always an integer. Thus the prime number would have factors, which is a contradiction. So odd prime numbers cannot be expressed as the sum of two or more consecutive odd numbers.

This leaves even numbers which are twice odd numbers, which cannot be expressed as the sum of two or more consecutive odd numbers. The easiest way to see this is by reference to the other answers which point out that numbers which can be expressed as the sum of consecutive odd numbers are always the difference of squares, and numbers which are twice odd numbers cannot be so expressed. If $b=2(2a+1)=4a+2$, then $b\equiv 2 \mod 4$. But $\forall n: n^2\equiv 0,1 \mod 4$ so $n_1^2-n_2^2 \equiv 0,1,3 \mod 4$

As an example of how an odd number can be represented as the sum of consecutive integers or consecutive odd integers in multiple ways, consider $$255=3\cdot 5\cdot 17=(127+128)=(84+85+86)=(49+50+51+52+53)=(7+8+9+10+11+12+13+14+15+16+17+18+19+20+21+22+23)=(83+85+87)=(47+49+51+53+55)$$