What loops are possible when doing this function to the rationals? What loops are possible when doing this function to the rationals?
Let's define this function on a simplified fraction $\frac{a}{b}$.
$$f\left(\frac{a}{b}\right)=\frac{a+b}{b+1}$$
I started this with $f(\frac{2}{3})=\frac{5}{4}$ then i did the function again and got this sequence of numbers $\frac{2}{3},\frac{5}{4},\frac{9}{5},\frac{7}{3},\frac{5}{2},\frac{7}{3},\dots$ I saw that is starts to loop with $\frac{7}{3},\frac{5}{2}$
Another loop is $\frac{1}{1}$, a one cycle.
Another loop I found was $\frac{2}{1},\frac{3}{2},\frac{5}{3}$.
My first question is: from starting from any rational number does it all ways end in a loop or does it ever go to infinity? And my second question is: what sizes of loops are possible?
If the three loops I stated are the only loops prove it
Dark made a post related What are the possible loops when doing this a type of function to the rationals?

Here is a modification of @Steven Stadnicki's proof. The novel contribution of this answer is justifying the reduction step in Steven's solution through the use of a suitable partial order on the set of lattice points.
Step 1. Settings and Useful Observations
Let $\mathbb{N}_1 = \{1, 2, 3, \dots\}$ denote the set of positive integers and define $\mathsf{Red} : \mathbb{N}_1^2 \to \mathbb{N}_1^2$ by
$$ \mathsf{Red}(a, b) = \frac{(a,b)}{\gcd(a,b)}. $$
Also, we equip $\mathbb{N}_1^2$ with the partial order $\leq$ such that1)
$$ (a, b) \leq (c, d) \quad \Leftrightarrow \quad [b < d]\text{ or }[b = d \text{ and } a \leq c]. $$
The following observations are easy to prove but will be useful throughout.

*

*$\text{(P1)} \ $ $a \leq c$ and $b \leq d$ implies $(a, b) \leq (c, d)$.


*$\text{(P2)} \ $ $\mathsf{Red}(\mathrm{p}) \leq \mathrm{p}$ for any $\mathrm{p} \in \mathbb{N}_1^2$.
Step 2. Key Observation
We will identify each pair $(a,b) \in \mathbb{N}_1^2$ satisfying $\gcd(a, b) = 1$ with the simplified fraction $a/b$. Under this identification, we have
$$f(a/b) = \mathsf{Red}(a+b,b+1). $$
Now we will investigate the effect of a suitable number of iterations of $f$. By noting that either $a$ or $b$ must be odd, the following three cases exhaust all the possibilities:

*

*Case 1. Suppose that both $a$ and $b$ are odd. Then both $a+b$ and $b+1$ are even, and so,
\begin{align*}
f(a,b)
= \mathsf{Red}(a+b, b+1)
= \mathsf{Red}(\tfrac{a+b}{2}, \tfrac{b+1}{2})
\stackrel{\text{(P2)}}\leq (\tfrac{a+b}{2}, \tfrac{b+1}{2}). \tag{1}
\end{align*}


*Case 2. Suppose that $a$ is odd and $b$ is even. Then by writing $d=\gcd(a+b,b+1)$,
\begin{align*}
f^{\circ 2}(a,b)
= f(\tfrac{a+b}{d},\tfrac{b+1}{d})
= \mathsf{Red}(\tfrac{a+2b+1}{d},\tfrac{b+d+1}{d}).
\end{align*}
Since $d$ is odd, both $a+2b+1$ and $b+d+1$ are even. This means that both are divisible by $2d$, and so,
\begin{align*}
f^{\circ 2}(a,b)
= \mathsf{Red}(\tfrac{a+2b+1}{2d},\tfrac{b+d+1}{2d})
\stackrel{\text{(P2)}}\leq (\tfrac{a+2b+1}{2d},\tfrac{b+d+1}{2d})
\stackrel{\text{(P1)}}\leq (\tfrac{a+2b+1}{2},\tfrac{b+2}{2}). \tag{2}
\end{align*}
Here, the last inequality follows from the general fact that $\frac{A+Bd}{d}\leq A+B$ for all $A, B \geq 0$ and $d \geq 1$.


*Case 3. Suppose that $a$ is even and $b$ is odd. Since $d = \gcd(a+b, b+1)$ is odd, we find that $\frac{a+b}{d}$ is odd and $\frac{b+1}{d}$ is even. So by applying $\text{(2)}$ and using the inequality in the previous step,
\begin{align*}
f^{\circ 3}(a,b)
= f^{\circ 2}(\tfrac{a+b}{d},\tfrac{b+1}{d})
\stackrel{\text{(2)}}\leq (\tfrac{a+3b+d+2}{2d},\tfrac{b+2d+1}{2d})
\stackrel{\text{(P1)}}\leq (\tfrac{a+3b+3}{2},\tfrac{b+3}{2}). \tag{3}
\end{align*}
Step 3. Proof
Let $(a, b) \in \mathbb{N}_1$ satisfy $\gcd(a, b) = 1$. Then by $\text{(1)}$–$\text{(3)}$, we observe the following:

*

*If $b > 3$, then $\frac{b+3}{2} < b$, and so, a suitable number of iterations by $f$ reduces the second coordinate. This can be repeated finitely many times until the second coordinate becomes $\leq 3$.


*If $b \leq 3$ and $a > 12$, then $\frac{a+3b+3}{2} < a$, and so, a suitable number of iterations by $f$ reduces the first coordinate. Similarly as before, this can be repeated finitely many times until the first coordinate becomes $\leq 12$.


*If $a \leq 12$ and $b \leq 3$, then a suitable number of iterations by $f$ will map $(a, b)$ into another point $(a', b')$ with $a' \leq 12$ and $b' \leq 3$. So by the pigeonhole principle, iteration by $f$ will eventually fall into a cycle.


*By checking all the possible $12+6+8=26$ cases manually, we find that there are only three types of cycles:
$$ (1, 1) \qquad (5, 2), (7, 4) \qquad (2, 1), (3, 2), (5, 3) $$
This completes the proof.

1) Note that this is exactly the colexicographical order induced by the usual order on $\mathbb{N}_1$.
