We consider all partitions of a positive integer n into a sum of (non-negative integer) exponents of 2 (i.e. 1,2,4,8,…). A number in the sum is allowed to repeat an arbitrary number of times (e.g. 7=2+2+1+1+1) and two partitions differing only in the order of summands are considered to be equal (e.g. 8=4+2+1+1 and 8=1+2+1+4 are regarded to be the same partition). Let E(n) be the number of partitions in which an even number of exponents appear an odd number of times and O(n) the number of partitions in which an odd number of exponents appear an odd number of times. For example, for n=5 partitions counted in E(n) are 5=4+1 and 5=2+1+1+1, whereas partitions counted in O(n) are 5=2+2+1 and 5=1+1+1+1+1, hence E(5)=O(5)=2. Find E(n)−O(n) as a function of n.
Solutions — 2
Solution 1
Let D(n)=E(n)−O(n). We trivially have O(1)=1 and E(1)=0, thus D(1)=−1, and E(2)=O(2)=1 (respectively 2=1+1 and 2=2), hence D(2)=0. We will show by total induction that D(n)=0 for all n>2. Assume it holds for all numbers from 2 to n−1. If n is odd, a partition must contain at least one 1. Since the addition of 1 changes the parity of the number of one's it follows that E(n)=O(n−1) and O(n)=E(n−1), hence since D(n)=−D(n−1)=0. If n is even the partition must contain an even number 2k of 1s. If it contains 2k=n or 2k=n−2, then we have the unique solutions 1+1+⋯+1 and 2+1+1+⋯+1, the first adding to E(n), the second to O(n). For other, smaller, values of k we note that the remaining exponents are all even, and we can thus apply the inductive hypothesis to 2n−2k. Thus, it follows that for even n we will also have D(n)=0. This completes the proof. □
Solution 2
Let G(x)=1+∑i=1∞D(i)xi be the generating function for the sequence we desire. To count partitions with an odd number of odd-appearing exponents as negative, we will multiply those choices as negative. Thus, we have that G(x)=(1−x+x2−x3+x4−…)(1−x2+x4−x6+x8−…)(1−x4+x8−x12+x16−…)…, where the i-term corresponds to choosing the number of times 2i−1 is represented in the partition. Taking the expression for each power series, one now finds G(x)=1+x11+x211+x411+x81… However, 1−xG(x)=1−x11+x11+x21⋯=1−x211+x211+x41⋯=1−x411+x411+x81⋯=⋯=1. Thus, G(x)=1−x from which it follows that D(1)=−1 and D(n)=0 for all n>1. □
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.
Source: MathNet,
licensed CC-BY-4.0.
Statement and solution reproduced as published; topic and difficulty added by this site.