Problem 3

For positive integer

k

, let

f(k)

be the number of integers in

\{k+1,\ldots,2k\}

whose binary expansion has exactly three

1

s. Prove every positive integer

m

occurs as

f(k)

, and determine all

m

for which exactly one

k

has

f(k)=m

Step 1 of 5: Track one step of the function

Previous step Next step

In plain words

Track one step of the function

f(k+1)-f(k)\in\{0,1\}

Detailed analysis

Passing from $k$ to $k+1$ removes $k+1$ and adds $2k+1$ and $2k+2$ . The binary expansion of $2k+2$ is that of $k+1$ followed by a zero, so these two contributions cancel. Therefore $f(k+1)=f(k)+1$ exactly when $2k+1$ has three $1$ s, and otherwise $f(k+1)=f(k)$ .