Let A be a subset of $\mathbb{R}$ with the following properties:
- $\frac{1}{2}\in{A}$ and
- If $x\in{A}$, then both $\frac{x}{2}\in{A}$ and $\frac{1}{1+x}\in{A}$.
Prove that $A$ contains all rational numbers in the interval $(0, 1)$, that is, if $r\in{(0,1)}$ with $r\in{\mathbb{Q}}$, then $r\in{A}$.
This problem has me stumped. It's easy to prove that if $\frac{2p}{q}\in{A}$ or $\frac{q-p}{p}\in{A}$, then $\frac{p}{q}\in{A}$, with $p<q$ and $p, q\in{\mathbb{N}}$, but I don't know where to take it from there.
Any hints or solutions would be appreciated. Bonus points for finding a costructive proof and for investigating whether picking any other rational other than $\frac{1}{2}$ would have worked.
Best Answer
Let $p/q$ be a rational number from the $(0,1)$. Let us show how we can get it from $1/2$. We apply the following procedure:
$(1)$ If $p/q$ can be reduced, we reduce it.
$(2)$ If $2p<q$ we multiply $p$ by $2$.
$(3)$ Otherwise we transform $p/q$ into $\frac{q-p}{p}$.
First, let us notice that the resulting number is also a rational number from $(0,1)$. Moreover, the denominator becomes smaller if we apply steps $1$ or $3$, and it doesn’t change if we apply step $2$. We can’t apply step $2$ endlessly though, so denominator will become smaller. And the numerator is smaller than the denominator.
If the denominator is $\geq 3$ than we still can apply one of the steps. Eventually, the denominator will become $2$. It can’t jump over $2$ straight to $1$ due to step $3$ because the numerator $1$ would have been multiplied by $2$. And it can’t get to $1$ due to step $1$ because the numerator is smaller. Since the numerator is smaller than the denominator, it will become $1$ on the same step.
An example: $18/23 \leftarrow 5/18 \leftarrow 10/18 \leftarrow 5/9 \leftarrow 4/5 \leftarrow 1/4 \leftarrow 2/4 \leftarrow 1/2$.