Prove ceil inequality with powers of 2 holds for all real numbers from $(1,2)$

Question

The problem statement is:

Given $r \in (1,2)$, show that there exist infinitely many $n \in \mathbb{N}$ such that $\lceil{nr}\rceil$ is a power of 2.

I tried a few specific examples and I realized that in order for $\lceil nr \rceil = 2^k $,

$\frac{2^k - 1}{r} < n \leq \frac{2^k}{r}$ must occur for infinitely many natural numbers k, and specifically, both sides of the inequality must have different whole number parts, aka $\lfloor\frac{2^k - 1}{r}\rfloor < \lfloor\frac{2^k}{r}\rfloor$

I tried $r = 1.5$ and I spotted a pattern in the decimal expansion that allowed me to deduce that this inequality holds for all odd $k$, but I can't find something in general.

Answer 1

We start by rewriting: $2^k=\lceil nr \rceil \iff 2^k-1<nr \le 2^k \iff n\le 2^k/r <n+1/r \iff \{2^k/r\} <1/r$

We now need to show that this is true for infinite many values of $k$.

We write $2^k/r=l+\phi, 2^{k+1}/r=m+\psi$ with $k,l\in Z$ and $0\le \phi,\psi<1$. We should write indices $k$, they are implied but not written.

Then $2l+2\phi=m+\psi \implies 2\phi-\psi\in Z$ and also $-1\le 2\phi-1<2\phi-\psi\le 2\phi <2$ hence $2\phi -\psi\in \{0,1\}$.

If $\psi=2\phi$ then $0\le \phi={{\psi}\over 2}<{1\over 2}<1/r$.

Hence we assume that $2\phi=\psi$ happens finitely often, or else we are done.

Then $\psi=2\phi-1$ for $k\ge K$. In other words $\phi_{k+1}=2\phi_k-1$ for $k\ge K$.

Let's consider the recurrent sequence $\phi_{k+1}=2\phi_k-1$ for $k\ge K$, then we should have $0\le \phi_k<1$ for all those $k$.

Then $0\le \phi_{k+1}=2\phi_k-1<\phi_k$ hence $\phi_k \downarrow \theta\ge 0$.

Taking the limit in $\phi_{k+1}=2\phi_k-1$ we find $\theta =2\theta -1 \implies \theta =1$, contradiction, since all terms $\phi_k$ with $k\ge K$ are at most $\phi_K<1$.

This solves the problem.