Monotone Functions – Finding x in R for Monotonicity of f(n) = {2^n * x}

Question

Find all $x \in \mathbb{R}$ such that $f: \mathbb{N} \rightarrow \mathbb{R}$, where $f(n) = \{2^n \cdot x\}$ (where $\{x\}$ denotes the fractional part of $x$), is increasing/decreasing on $\mathbb{N}$.

My approach
We have $f(n+1) = \{2f(n)\}$, where $f(n+1)$ equals $2f(n)$ when $f(n) \in [0, \frac{1}{2})$ and equals $2f(n)-1$ when $f(n) \geq \frac{1}{2}$.

Thus, we have three cases:
Case 1: When $f(0) = 0$, implying $f(n) = 0$ for every $n$. This means $x$ is an integer.
Case 2: When $f(0) \in (0, \frac{1}{2})$. Case 3: when $f(0) \geq \frac{1}{2}$, we encounter a contradiction.

However, it seems that $x$ can also be in the form $a – \frac{1}{2^m}$, but I'm not sure how to obtain this solution. I may have did something wrong at case 1 or 3 that made me miss that solution. Any help is appreciated.

Answer 1

Since it's not mentioned how the fractional part is defined for $x<0$ so I'll solve for nonegative $x$ first.

Let $r = \{x\}$ be the fractional part of $x$, it's clear that $\{2^nx\} = \{2^nr\}$. Notice that $\left \lfloor 2^nr \right \rfloor$ corresponds to the first n fractional digits of r in the binary system, and $\left \lfloor 2^nr \right \rfloor$ corresponds to what's left. So for example $r = 0.11101_2$, then $\left \lfloor 2^nr \right \rfloor = 11_2$ and $\left \{ 2^nr \right \} = 0.101_2$

Let $d_i(r)$ for $i \in \mathbb{N_+}$ be the $i$-th fractional digit of r, $\mathbf{0}(r) = \min \left\{k \in \mathbb{N_+} \mid d_k(r) = 0\right\}$, $\mathbf{1}(r) = \min \left\{k \in \mathbb{N_+} \mid d_k(r) = 1\right\}$ be the index of the first $0$ or $1$ fractional digit respectively.

If $r = 0$, then $f(n) = \{2^nx\} = 0$ so it's clearly monotonic

If $r > 0$, let $k = \mathbf{1}(r)$. There are two cases:

1. If $f(n)$ is monotonically increasing, Then $f(k-1) \geq 0.1_2$. Since $f(n)$ is monotonic $f(k) \geq f(n) \geq 0.1_2$, therefore the $d_{k+1}(r) = 1$. Inductively, all digits starting from the $k$th digit is also $1$. Which means $r = 0.00...01111..._2$ with $k$ leading zeros. But this also makes $r = 2^{-k}\sum_{n=1}^{\infty}{2^{-n}} = 2^{-k+1}$ which is $0.00...1_2$ with $k-1$ leading zeros (contradiction)
2. If $f(n)$ is monotonically decreasing, then any digit before the $k$-th must also be $1$, but it's the first one so there is none, hence $k = 1$. Let $l = \mathbf{0}(r)$. By using an argument similar to point 1, all trailing digits after the $l$-th digit are 0. Hence $r = 0.111...1_2$ with $(l-1)$ of $1$ digits. Therefore $r = 1 - 2^{-l+1} = 2^{-t}$, $t = l-1$

In conclusion, $x \in \left\{n, n+1-2^{-t}\right\}$ where $n,t \in \mathbb{N}, t>0$

EDIT: No digit system version

Case 1: If $r = 0$, $f(n) = 0$

Case 2: If $r > 0$:

Let $k = \lceil -log_2{r} \rceil$, then $k \geq 1$ and $-log_2{r} + 1 > k \geq -log_2{r}$ .

Therefore $2 > 2^kr \geq 1 \Rightarrow 1 > 2^{k-1}r \geq 1/2 $

Consequently $ f(k) = \{2^{k}r\} = 2^{k}r - 1$ and $ f(k-1) = \{2^{k-1}r\} = 2^{k-1}r$

$ \Rightarrow f(k) - f(k-1) = 2^{k}r - 1 - 2^{k-1}r = 2^{k-1}r-1 \leq 0$

Case 2.1: If $r = 2^{-k}$ then $k$ must be $1$

Case 2.2: If $r > 2^{-k}$ then $f(k) - f(k-1) < 0$, the function must be monotonically decreasing

If $k > 1$, then $k-2$ is a natural number, and $f(k-2) = f(k-1)/2 < f(k-1)$, which is contradiction. Therefore $k = 1$ and $r \geq 1/2$

Let $\epsilon = 1-r$, $l=\lfloor -log_2(\epsilon) \rfloor$, then $2^{-l} \geq \epsilon > 2^{-l-1}$. For $n \leq l$ we have $$f(n) = \{2^n(1-\epsilon)\} = \left\{2^n-1+1-2^n \epsilon \right\} = 1-2^n \epsilon$$

hence $f(n)$ decreases.

Since $\epsilon > 2^{l-1}$, $f(l) < 1/2$. Therefore $f(l+1)$ = $2f(l)$. Since $f(l+1)\leq f(l)$, then $f(l) \leq 0 \Rightarrow f(l) = 0 \Rightarrow \epsilon = 2^{-l} \Rightarrow r = 1-2^{-l}$

Conclusion: $r \in \{1-2^{-l}\mid l\in\mathbb{N}\}$