Solved by Dave Newquist

Question:

Find all positive integers that are not expressible as the sum of (at least two) consecutive positive integers. You have to prove your answer is correct! Hint: try to answer the question for small integers and it should become clear very quickly what the answer is. Proving it may be more difficult.

Answer:

Finding numbers that can not be expressed as a sum of 2 or more positive integers is easy, proving that all other integers can be expressed as a sum of 2 or more positve integers is the real challenge.

Assume (towards a contradiction), that we have a sum of k (k>1) consecutive integers starting at n that equals 2^i. So n + (n+1) + (n+2) +...+ (n+k-1) = 2^i.

Grouping the n's together yields

n*k + 1 +2+...k-1 = 2^i

Using the formula for the sum of the first k-1 integers we have

n*k +((k-1)^2 +k-1)/2 = 2^i

multiplying by 2 on both sides and factoring out a k on the left side yields

k(2n +k -1) = 2^(i+1)

Now we can see a dilemna. 2^(i+1) has no odd factors, but if k is even, then 2n +k -1 is odd! (even + even -1 = odd)

Now, for any n (n is not equal to 2^i for some i) we will give a method for finding a sequence of 2 or more consecutive integers such that their sum is n. If n is odd, then we can easily find our sequence. It is simply the floor and ceiling of n/2.

The real trick is finding the sequence when n is even. Let n be expressed as d*2^k for some odd d. Let d_f be the floor of d/2. So d = d_f + (d_f +1). This is true because 2*d_f = d-1. We will now show that we can always find another sequence of integers such that its sum is d*x (for all x >1).

For the original sequence, include (d_f -1) and (d_f+2) if d>3. If d is equal to 3, then d_f = 1, and we handle this case below. Since (d_f -1) + (d_f+2) = d, the sum of the new sequence is d*2. Unless the smallest element of the sequence is 1, then we can always increase this sequence by d if we include the next smallest integer and the next largest in the sequence. If the smallest number is 1, then we use a different method for finding a new sequence that is d more than the previous. If the smallest integer in the sequence is 1, then we must have all of the integers up to d_f in the sequence (we added (d_f -1) integers. Since we included another integer greater than (d_f +1) every time we included one smaller than d_f, we must have included the next (d_f-1) integers after (d_f +1). Since (d_f -1) + (d_f +1) = 2*d_f = d-1, we have a sequence of the first d-1 integers, which are a multiple of d.
(Side note: Wow! I guess the sum of the first n-1 integers is a multiple of n if n is odd. Cool!)

So to increase this sequence by d again, just include d. Since we have a sequence of d integers, we can increase by d again if we add 1 to each integer. Now we can repeat this step to get a sequence of d consecutive integers whose sum is any multiple of d, ad infinatum.

At this point we have show that a positive integer is expressible as a sum of consecutive positive integers if and only if the integer is not 2^i (for all i >=0). QED

-- Dave Newquist