This problem is from a Turkish contest:
Let $P(x)=x+1$ and $Q(x)=x^2+1$.
Consider all sequences $(x_k,y_k)$ such that $(x_1,y_1)=(1,3)$ and
$(x_{k+1},y_{k+1})$ is either $(P(x_k),Q(y_k))$ or $(Q(x_k),P(y_k))$.Find all positive integers $n$ such that $x_n=y_n$ holds in at least one of these sequences.
Clearly, $n=3$ is one possibility ($(x_2,y_2)=(2,4)$, $(x_3,y_3)=(5,5)$) and it seems to be the only one, but I don't know how to proceed in the general case.
Any help would be appreciated, thanks.
Let $f(x)=x^2+1$. If $x_k=y_k$ with $k\ge4$, we have $x_{k-1}=y_{k-1}^2$ or $y_{k-1}=x_{k-1}^2$. We will only consider $x_{k-1}=y_{k-1}^2$ and let $(x_1,y_1)$ be $(1,3)$ or $(3,1)$ both possible.
We will prove via induction $$x_{k-t-1}+t=f^t(y_{k-t-1})^2\tag{1}$$ for all $t\le k-2$. For $t=1$, from $x_{k-1}=y_{k-1}^2$ $$x_{k-2}+1=(y_{k-2}^2+1)^2=f(y_{k-2})^2\text{ or }x_{k-2}^2+1=(y_{k-2}+1)^2$$ The second case is impossible since $y_{k-2}+1\ge2$ so the first case must be true. So $(1)$ is true for $t=1$.
Now Assume $(1)$ true for $t=u$ where $1\le u\le k-3$. We must have $$x_{k-u-2}+u+1=f^{u+1}(y_{k-u-2})^2\text{ or }x_{k-u-2}^2+u+1=f^u(y_{k-u-2}+1)^2$$ First consider the second case. Since $a^2-b^2\ge 2a-1$ for all $a>b$, we have$$u+1=f^u(y_{k-u-2}+1)^2-x_{u-k-2}^2\ge2f^u(y_{k-u-2}+1)-1\ge2f^u(2)-1>2(2+u)-1$$ which is a contradiction. So the second case must be true which means $(1)$ is also true for $t=u+1$.
So $(1)$ is true for $t=k-2$. Which means $x_1+k-2=f^{k-2}(y_1)^2$. But this is impossible since $$k+1\ge x_1+k-2=f^{k-2}(y_1)^2\ge f^{k-2}(1)^2=f^{k-4}(5)^2\ge(5+(k-4))^2>k+1$$ Thus we cannot have $k\ge 4$. For $k\le 3$, we can easily check that $k=3$ is only possible with $(x_2,y_2)=(2,4),(x_3,y_3)=(5,5)$.