Show that the set can describe all rational numbers in (0, 1). Let A be a subset of (0, 1) ∩ Q, where Q is the set of all rational numbers.
Given that $\frac{1}{2}\in A$ and that $\frac{x}{x+1},\frac{1}{x+1}\in A$ if $x\in A$, show that A = (0, 1) ∩ Q.
What I've tried to do:
For simplicity, let (1) be the operation $x\rightarrow\frac{x}{x+1}$, and (2) the other one $x\rightarrow\frac{1}{x+1}$. As we have only fractions in A, (1) can be rewritten as $\frac{x}{y}\rightarrow\frac{x}{x+y}$, and (2) as $\frac{x}{y}\rightarrow\frac{y}{x+y}$
Basically, we need to show that $\frac{a}{b}\in A $ for each a, b - natural numbers with a < b. For this, I figured out I need to show that I can make any $\frac{a}{b}$ using (1) and (2) on $\frac{1}{2}.$ The 'a < b' part is obvious as (1) and (2) only increases the denominator.
We can easily prove that we can make any $\frac{1}{n}$, where $n\geq2$ by applying (1) on $\frac{1}{2}$ (n-2) times.
After this, I proved that we can make any $\frac{F_{k+1}n+F_k}{F_{k+2}n+F_{k+1}}$ by applying (2) on $\frac{1}{n}$ (k) times, where I noted with $F_k$ - the kth number in the sequence {0, 0, 1, 1, 2, 3, 5, 8...} (the Fibonacci numbers).
After testing some examples, I arrived at the conclusion that I can write any $\frac{a}{b}$ by applying (1) on $\frac{F_{k+1}n+F_k}{F_{k+2}n+F_{k+1}}$ a specific number of times but I couldn’t prove this. I got this problem from a set of problems based on induction so I think it can be solved using it.
 A: You can do it by induction on the denominator. That is, we can show that, for all $0 < a < n$, we have $\frac{a}{n} \in A$, and we show this by induction on $n \ge 2$. Clearly the result holds for $n = 2$, by our assumption that $\frac{1}{2} \in A$.
Suppose that, for some $n \ge 3$, we have $\frac{a}{k} \in A$, whenever $0 < a < k < n$. Now, suppose $0 < a < n$. Let's solve the two equations:
\begin{align*}
\frac{1}{x + 1} = \frac{a}{n} &\iff x = \frac{n - a}{a} \\
\frac{x}{x + 1} = \frac{a}{n} &\iff x = \frac{a}{n - a}.
\end{align*}
Note that at one of the two solutions is a rational number in $(0, 1)$, and both have denominators strictly less than $n$. If $a > n - a \iff a > \frac{n}{2}$, then the first solution lies in $(0, 1)$ and hence in $A$ by the induction hypothesis. If $a < n - a \iff a < \frac{n}{2}$, then the second solution lies in $A$. If $a = n - a \iff a = \frac{n}{2}$, then $\frac{a}{n} = \frac{1}{2} \in A$ by assumption.
Either way, by strong induction, the result holds.
