3

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.

Stanislav Brega
  • 33
  • I believe you have misunderstood the operations. Repeatedly applying $x\ \mapsto\ \frac{1}{x+1}$ to the initial value of $\tfrac12$, you get the sequence $\tfrac12$, $\tfrac{2}{3}$, $\tfrac{3}{5}$, $\tfrac{5}{8}$, etcetera. – Servaes Nov 18 '21 at 20:14
  • Sorry. I've edited the question. I've confused (2) with (1) in 2 paragraphs. – Stanislav Brega Nov 18 '21 at 20:21

1 Answers1

2

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.

Theo Bendit
  • 50,900
  • So, if a/k is our induction hypothesis, we can say that one of the x values (depending on either a is bigger than n) can be formed from a fraction smaller or equal to a/k by strong induction? – Stanislav Brega Nov 18 '21 at 21:59
  • 1
    Not quite. We assume $\frac{a}{k}\in(0, 1)\cap\Bbb{Q}$ is also in $A$ whenever $k<n$; that's our (strong) induction hypothesis. We then consider $\frac{a}{n}\in(0, 1)\cap \Bbb{Q}$, with the aim to show that it is in $A$. We consider the cases where $\frac{a}{n}<\frac{1}{2}$, $\frac{a}{n}=\frac{1}{2}$, or when $\frac{a}{n}>\frac{1}{2}$, and in each case, we can write $\frac{a}{n}$ as $\frac{1}{2}$, as $\frac{1}{x+1}$ for some $x \in A$, or as $\frac{x}{x + 1}$ for some $x \in A$ (in each case, $x\in(0, 1)\cap\Bbb{Q}$ with denominator strictly smaller than $n$). In all cases, $\frac{a}{n}\in A$. – Theo Bendit Nov 18 '21 at 22:38