Find the number of positive integers such that for some strictly increasing sequence of nonnegative integers . For example, we may write and , but 4 cannot be written in this form.
Solution
Clearly must be even, or the sum would be negative. Furthermore, if , the sum cannot exceed since . Likewise, if , then the sum necessarily exceeds , which is not hard to see by applying the Triangle Inequality and summing a geometric series. Hence, the elements of can be any subset of with an odd number of elements. Since the number of even-sized subsets is equal to the number of odd-sized elements, there are such subsets. Now, it suffices to show that given such an , the value of can only be obtained in this way. Suppose for the sake of contradiction that there exist two such sequences and which produce the same value of for positive or negative, where we choose such that is as small as possible. Then, we note that since , we have that . Similarly, we get that ; for the two to be equal, we must have . However, this means that the sequences obtained by removing and from have smaller maximum value but still produce the same alternating sum, contradicting our original assumption.