What is the set generate by ${1}$ and a function $1/(a+b)$?

Question

If I'm given a starting set, and an operation, what would the generated set looks like?

Here we take $S_0=\{1\}$ and $f(a,b) = \dfrac{1}{a+b}$ as an example, the following Mathematica codes shows the recursion:

S = {1};
S = Union[S, 1/(#1 + #2) & @@@ Tuples[S, 2]] // Sort // 
  DeleteDuplicates

after the second step, I get $S_1=\{1,1/2\}$, $1/2 = 1/(1+1)$ and after the third step, I get $S_2=\{1,1/2,2/3\}$, $2/3=1/(1+1/2)$ then after the fourth step, I get $S_3=\{1/2,3/5,2/3,3/4,6/7,1\}$...

I can prove that the max and min of the final set is 1 and 1/2 respectively, and I guess it would contain all rational numbers between 1/2 and 1. Is my guess true? And how to prove it true? Generally, how to analyse this kind of generating problems?

Answer 1

It is clear that every number in $S$ is a rational number between $\tfrac12$ and $1$ inclusive. For any rational number $r$ define the height $h(r)$ as its minimal denominator, so that $h(\tfrac ab)=b$ if $\gcd(a,b)=1$. We prove by induction that $S$ contains every rational number in the closed interval $[\tfrac12,1]$.

The base case $h(r)=1$ is clear; the only rational number of height $1$ in $[\tfrac12,1]$ is of course $1$, and $1\in S$ by definition. So let $n>1$ and suppose that $S$ contains every rational number $r\in[\tfrac12,1]$ with $h(r)<n$.

Let $r\in[\tfrac12,1]$ with $h(r)=n$, so that $r=\tfrac mn$ for some positive integer $m$ with $\gcd(m,n)=1$ and $n\leq 2m\leq 2n$. Because $n>1$ and $\gcd(m,n)=1$ it follows that $m<n$. Then for any integer $k$ with $m\leq 2k\leq 2m$ we have $\tfrac km\in[\tfrac12,1]$ and $h(\tfrac km)\leq m<n$, so by induction hypothesis $\frac{k}{m}\in S$. It follows that $S$ also contains $$\frac{1}{\frac{k_1}{m}+\frac{k_2}{m}}=\frac{m}{k_1+k_2},$$ so it suffices to write $n=k_1+k_2$ with $m\leq 2k_i\leq 2m$. If $n=2k$ we may take $k_1=k_2=k$, if $n=2k+1$ we may take $k_1=k$ and $k_2=k+1$.

Answer 2

Let $S$ be the smallest set containing $1$, such that for any $a, b \in S$, we have $f(a, b) \in S$. I'll show by induction on $n$ that for positive integers $m, n$ with $\frac 12 \le \frac mn \le 1$, we have $\frac mn \in S$.

Indeed, we can assume that $\frac 12 < \frac mn < 1$, since it's clear that $\frac 12, 1 \in S$. In particular we can assume $m < n$ and $n < 2m$.

• If $n$ is even, say $n = 2k$. Observe that $\frac mn = f(\frac km, \frac km)$, and $\frac 12 \le \frac km \le 1$:
  • We have $m < n = 2k$, so $\frac 12 < \frac km$.
  • We have $2k = n < 2m$, so $\frac km < 1$.
• If $n$ is odd, say $n = 2k + 1$. Observe that $\frac mn = f(\frac km, \frac{k + 1}m)$, and $\frac 12 \le \frac km \le \frac{k + 1}m \le 1$:
  • We have $m < n = 2k + 1$, so $m \le 2k$, so $\frac 12 \le \frac km$.
  • We have $2k + 1 = n < 2m$, so $2k + 2 \le 2m$, so $\frac {k + 1}m \le 1$.

In each case, we have written $\frac mn$ as an output of inputs between $\frac 12$ and $1$ that have strictly smaller denominator (which must belong to $S$ by inductive hypothesis). So we are done.

I'm afraid I don't have much to say about general techniques! In this case you might come across this proof by observing what combinations lead to what fractions and spotting a pattern there.