For each positive integer n, let f(n) denote the number of ways of representing n as a sum of powers of 2 with non-negative integer exponents. Representations which differ only in the ordering of their summands are considered to be the same. For example, f(4) = 4, because 4 can be represented as 4, 2 + 2, 2 + 1 + 1 or 1 + 1 + 1 + 1. Prove that for any integer n ≥ 3, 2n2/4 < f(2n) < 2n2/2.
Solution
The key is to derive a recurrence relation for f(n) [not for f(2n)]. If n is odd, then the sum must have a 1. In fact, there is a one-to-one correspondence between sums for n and sums for n-1. So:
f(2n+1) = f(2n)
Now consider n even. The same argument shows that there is a one-to-one correspondence between sums for n-1 and sums for n which have a 1. Sums which do not have a 1 are in one-to-one correspondence with sums for n/2 (just halve each term). So:
f(2n) = f(2n - 1) + f(n) = f(2n - 2) + f(n).
The upper limit is now almost immediate. First, the recurrence relations show that f is monotonic increasing. Now apply the second relation repeatedly to f(2n+1) to get:
f(2n+1) = f(2n+1 - 2n) + f(2n - 2n-1 + 1) + ... + f(2n - 1) + f(2n) = f(2n) + f(2n - 1 ) + ... + f(2n-1 + 1) + f(2n) (*)
and hence f(2n+1) ≥ (2n-1 + 1)f(2n)
We can now establish the upper limit by induction. It is false for n = 1 and 2, but almost true for n = 2, in that: f(22) = 222/2. Now if f(2n) ≤ 2n2/2, then the inequality just established shows that f(2n+1) < 2n2n2/2 < 2(n2+2n+1)/2 = 2(n+1)2/2, so it is true for n + 1. Hence it is true for all n > 2.
Applying the same idea to the lower limit does not work. We need something stronger. We may continue (*) inductively to obtain f(2n+1) = f(2n) + f(2n - 1) + ... + f(3) + f(2) + f(1) + 1. (**) We now use the following lemma:
f(1) + f(2) + ... + f(2r) ≥ 2r f(r)
We group the terms on the lhs into pairs and claim that f(1) + f(2r) ≥ f(2) + f(2r-1) ≥ f(3) + f(2r-2) ≥ ... ≥ f(r) + f(r+1). If k is even, then f(k) = f(k+1) and f(2r-k) = f(2r+1-k), so f(k) + f(2r+1-k) = f(k+1) + f(2r-k). If k is odd, then f(k+1) = f(k) + f((k+1)/2) and f(2r+1-k) = f(2r-k) + f((2r-k+1)/2), but f is monotone so f((k+1)/2) ≤ f((2r+1-k)/2) and hence f(k) + f(2r+1-k) ≥ f(k+1) + f(2r-k), as required.
Applying the lemma to (**) gives f(2n+1) > 2n+1f(2n-1). This is sufficient to prove the lower limit by induction. It is true for n = 1. Suppose it is true for n. Then f(2n+1) > 2n+12(n-1)2/4 = 2(n2-2n+1+4n+4)/4 > 2(n+1)2/4, so it is true for n+1.
© John Scholes
jscholes@kalva.demon.co.uk
22 Oct 1998
Last corrected/updated 21 Aug 03