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 3 of 5: Characterize a unique

k

Previous step Next step

In plain words

Characterize a unique $k$

2k-1\text{ and }2k+1\text{ have three }1\text{s}\iff k-1\text{ and }k\text{ have two }1\text{s}

Detailed analysis

Because increments are $0$ or $1$ , $f(k)=m$ is unique exactly when both adjacent increments are $1$ , i.e. when $2k-1$ and $2k+1$ each have three $1$ s. Appending or removing the last binary digit shows this is equivalent to $k-1$ and $k$ each having two $1$ s.