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 2 of 5: Record monotonicity

Previous step Next step

In plain words

Record monotonicity

f(N)\le f(N+1)

Detailed analysis

The recurrence shows that $f$ is nondecreasing. Iterating $f(2r)=f(2r-2)+f(r)$ gives $f(2N)=\sum_{j=0}^{N}f(j)$ . Hence $f(2^{n+1})<(2^n+1)f(2^n)$ for $n\ge2$ , because the sum has $2^n+1$ terms and all terms except the harmless $j=0$ are at most $f(2^n)$ .