Problem 6

For each positive integer

N

, let

f(N)

be the number of ways to represent

N

as a sum of powers of

2

with non-negative integer exponents; order of summands is ignored. For example,

f(4)=4

. Prove that for every integer

n\ge3

2^{n^2/4}<f(2^n)<2^{n^2/2}

Step 3 of 5: Prove the upper bound

Previous step Next step

In plain words

Prove the upper bound

f(2^n)<2^{n^2/2}

Detailed analysis

The base case $f(8)=10<2^4$ holds. If $f(2^n)<2^{n^2/2}$ , then $f(2^{n+1})<(2^n+1)2^{n^2/2}<2^{(n+1)^2/2}$ , since $2^n+1<2^{n+1/2}$ . Induction proves the upper inequality.