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 4 of 5: Use the pairing lemma

Previous step Next step

In plain words

Use the pairing lemma

\sum_{j=1}^{2r}f(j)\ge2r f(r)

Detailed analysis

Pair the terms symmetrically. The recurrence shows $f(j)+f(2r+1-j)$ is nonincreasing as $j$ moves from $1$ to $r$ , so every pair is at least $f(r)+f(r)=2f(r)$ . This proves the lemma.