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

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.

• Look at the binary expansion of $r^{-1} = 0.1{\cdots}$. Note that multiplying by $2^k$ shifts the binary point $k$ places to the right.
– WimC
Commented Sep 7, 2022 at 5:22

We start by rewriting: $$2^k=\lceil nr \rceil \iff 2^k-1

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.