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 5 of 5: Prove the lower bound

Previous step Next step

In plain words

Prove the lower bound

f(2^{n+1})>2^n f(2^{n-1})

Detailed analysis

Iterating the recurrence for $f(2^{n+1})$ and applying the pairing lemma to the resulting block gives $f(2^{n+1})>2^n f(2^{n-1})$ . Starting from $f(2)=2$ and $f(4)=4$ , induction yields $f(2^n)>2^{n^2/4}$ for every $n\ge3$ .