Problems of Ukrainian Authors

Let $(a_n)$ be the sequence of all natural numbers $k$ that in binary representation have $1$s only on even places or only on odd places. For instance, this sequence contains the numbers that have the following binary representations: $10000$, $10100$, $101$, $1000$. Evidently, the first condition is satisfied for this sequence. We will show that the estimate from the second condition is also valid.

Consider all non-negative numbers that are less than $2^{2r}$, that is the numbers that have no more than $2r$ digits in their binary representations. We count the number of elements of our sequence among these numbers: there are $2^r$ elements that have $0$s on all even places and $2^r$ elements that have zeros on all odd places, and zero is the only number that was counted twice. Hence, there are $2^{r+1}-1$ elements of our sequence that are less than $2^{2r}$ and so $a_{2^{r+1}-1}=2^{2r}$.

For any natural number $n$ we can find an integer $r$, such that: $2^{r+1}-1\le n<2^{r+2}-1$. Then we have: $2^r>\frac{n}{4}\Rightarrow a_n\ge a_{2^{r+1}-1}=2^{2r}>\frac{n^2}{16}$, and we are done.