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 1 of 5: Derive the recurrence

Previous step Next step

In plain words

Derive the recurrence

f(2r+1)=f(2r),\quad f(2r)=f(2r-2)+f(r)

Detailed analysis

An odd total must contain a $1$ , and removing one gives the first identity. For an even total, representations containing a $1$ correspond to those of one less even total, while representations without a $1$ halve to representations of $r$ ; this gives the second identity.