Problem:
Let be the number of ways to write as a sum of powers of 2 , where we keep track of the order of the summation. For example, because 4 can be written as , , and . Find the smallest greater than 2013 for which is odd.
Solution:
Solution 1: The answer is 2047. We shall prove that is odd iff for . It is easy to see that , and . Assume that the statement holds true for . We will show that the statement is true for .
Let be an integer such that .
If we write for . We see that . By induction hypothesis each of is even, but is odd, so is even.
If we have .
By induction hypothesis each term on the right hand side is odd iff for some positive integer . For each of the form these odd summands appear in pairs: and . Therefore is odd iff , that is iff .
Solution 2: The answer is 2047. We show that is odd if and only if is of the form .
We use the method of generating functions. Define the formal power series . The desired statement can be interpreted as
where the congruence means that the difference between the two sides has all coefficients divisible by 2. It is equivalent to prove the same thing after clearing denominators, in other words,
But this holds because (all the cross terms in the expansion of being even), so
This problem and solution were suggested by Kiran Kedlaya and David Speyer.
Solution 3: Consider the operation of reversing the order of the sums. Call a sum a palindrome if it is invariant under this symmetry and let be the number of palindromic decompositions of . Since non-palindromic sums are paired under reversing order we have
Now suppose is odd. By parity a palindromic decomposition of must have an odd central term (and in particular cannot have even length). Hence the central term must be 1 . Thus any palindromic decomposition of starts with an arbitrary decomposition of , followed by a 1 and the reverse of the starting decomposition. Thus
Hence .
Now suppose is even and positive. Then there are two kinds of palindromic decompositions of . The first kind have even length. The second kind have odd length and a central element that is even, hence for some . These two kinds occur equally often since we can add together the two equal terms of a palindrome of equal length into two equal halves to reverse this operation. Thus and are even.
These two cases easily imply is odd if and only if is 1 less than a power of 2 . One way to see this is to write in binary. The first rule says the parity of is unchanged if we delete a least significant digit of 1 . The second rule says is even if its least significant digit is zero. Iterating these we see is odd if and only if its binary representation is all 1 s, that is, is 1 less than a power of 2 .
This solution was suggested by Steven Blasberg and Richard Stong.
The problems on this page are the property of the MAA's American Mathematics Competitions