Let a sequence of natural numbers be $a_{n+2}=\frac{a_{n+1}+a_n}{\gcd\left(a_{n+1,}a_n\right)}$ where $a_1=a,a_2=b$. Find all such pairs of $a,b$ such that the sequence is bounded.
Denote $\gcd(a,b)=(a,b)$. First of all, I notice if $(a,b)=1$ then the sequence would grow like $a+b,a+2b,....$, so $(a,b)=d>1$. Now let $a=dx,b=dy$ and $(x,y)=1$. Then we get $a_3= x+y$ so, $a_4=\frac{x+y+b}{(x+y,b)}$. How do I proceed?
On
The solution given by @Aig is very elegant but I think there is another solution that completes the idea mentioned by the OP.
Let's assume $a_1,a_2,a_3 , ... \ $is bounded.
As the OP noticed, we must have $a_1=d_1x_1$ and $a_2=d_1y_1$ where $(x_1,y_1)=1$ and $d_1>1.$ Then, we have $a_3=x_1+y_1$ and we must also have $(a_2,a_3)=d_2>1$.
Since $(x_1,y_1)=1$, we will have $d_2|d_1$ (in fact $(d_2,y_1)=1$). We can suppose $a_2=d_2x_2$ and $a_3=d_2y_2$, where $(x_2,y_2)=1$. Now, we have $a_4=x_2+y_2$ and we must also have $(a_3,a_4)=d_3>1.$
Again, since $(x_2,y_2)=1$, we will have $d_3|d_2$ (and consequently $d_3|d_1$). Again, we suppose $a_3=d_3x_3$ and $a_4=d_3y_3$, where $(x_3,y_3)=1$.
Doing the same procedure infinitely many times, we obtain a non-increasing sequence $d_1,d_2,d_3, ... \ $ such that for every $i \in \mathbb N$, we have $d_i|d_1$. That means the sequence $d_1,d_2,d_3, ... \ $ is constant, from some point on; let's say the sequence is eventually equal to $d$. Thus, from some point on, the sequence $a_1,a_2,a_3 , ... \ $ can be considered as below:
$$dm_1,dm_2,dm_3, ... \ ,$$
such that $(m_i,m_{i+1})=1$ for every $i \in \mathbb N$.
Moreover, by the way the sequence is generated, we must have:
$$m_1+m_2=dm_3, \\ m_2+m_3=dm_4, \\ .\\ .\\ .\\ m_{j-1}+m_{j}=dm_{j+1}.$$
So,
$$m_1+2m_2+2(m_3+...+m_{j-1})+m_j=d(m_3+...+m_{j-1})+d(m_j+m_{j+1}) \\ \implies (d-2)(m_3+...+m_{j-1})=m_1+2m_2+m_j-d(m_j+m_{j+1}).$$
Note that the identity above holds for every $j$ and the right hand of the identity is bounded (because the original sequence is bounded) while the left hand diverges if $j \to \infty$. Therefore we must have $d-2=0 \implies d=0.$
Having $d=2$ implies that the sequence $a_1,a_2,a_3 , ... \ $, from some point on, is as below:
$$x,y, \frac{x+y}{2}, \frac{\frac{x+y}{2}+y}{2}, \frac{\frac{\frac{x+y}{2}+y}{2}+\frac{x+y}{2}}{2}, ...,$$
which is bounded. However, note that all the elements of the sequence above are distinct if $x \neq y$ (simply because every element is the mean of two other elements). That's clearly a contradiction unless $x=y$. In this case, we have:
$$x=y \implies 2=d=(x,y)=x \implies x=y=2.$$
Thus, the sequence must be eventually $2,2,2, ... \ .$
We are done.
I will denote a pair of neighbour numbers from the sequence $(a_n)$ as $x,y$ going in that order. As you already stated, once we get a pair of coprime $x,y$, the sequence is done: it strictly increases after and hence is unbounded. Indeed, $\frac{x+y}{\gcd(x,y)}= x+y > y$ and new pair numbers $y, x+y$ are also coprime.
Next, let us assume that $x=y=2$. What number (denote it by $t$) was before $x$ in the sequence? Here is the equation for $t$:
$$\frac{t+2}{\gcd(t,2)}=2.$$ If $t$ is odd then $\gcd(t,2)=1$ and $t=0$ which is impossible. If $t$ is even then $\gcd(t,2)=2$ and $t=2$. So, the whole sequence only consists of $2$ and is bounded. Thus, we get the only suitable pair of $a,b$. The answer to this problem is $a=b=2.$
Now, let us assume that every pair $x,y$ in the sequence is such that at least one of the numbers $x,y$ is not $2$ and $\gcd(x,y)\neq 1$. Consider the number $t$ following after $y$. We will prove that $\max(x,y)\ge\max(y,t)$. Indeed,
$$\max(y,t)= \max(y,\frac{x+y}{\gcd(x,y)}) \le \max(y,\frac{2\max(x,y)}{2})=$$ $$ = \max(y,\max(x,y))=\max(x,y).$$
The equality $\frac{x+y}{\gcd(x,y)} = \frac{2\max(x,y)}{2}$ happens only if $x=y$ and $\gcd(x,y)=2$, so if $x=y=2$, which is not the case here. Hence $t=\frac{x+y}{\gcd(x,y)} < \frac{2\max(x,y)}{2}=\max(x,y)$. If $\max(y,t)=\max(x,y)$ then $\max(y,t)=y\implies t<y$. And also $y\ge x$.
This means that pairs get “smaller” and “smaller”. Even if $\max(x,y)=\max(y,t)$ the next pair will get “smaller” since $t<y$.
But it can’t be so that the pairs get “smaller” endlessly. Therefore, sooner or later $\gcd(x,y)$ will become $1$ unless the sequence was all $2$s.