Find all the pairs $(n,n)$ that we can obtain with these operations It's a problem from some competition: Given $(a,b)\in\mathbb{N}^2$ we can do the following operations: $(a^2+1,b+1)$ and $(a+1,b^2+1)$. Find all $n\in\mathbb{N}$ such that from the pair $(1,3)$ and throught a sequence of operations we get $(n,n)$.
These are my tries and observations:
First I notice that if we have to end at $(n,n)$ then $a^2+1=b+1$ or $a+1=b^2+1$ these are symetrical conditions and implies that $a^2=b$ or $a=b^2$.
If we get $(n,n)$ from two operations, $(a,b)\rightarrow(a+1,b^2+1)\rightarrow(n,n)$ we find that
$(a+1)^2=b^2+1$ or $a+1=(b^2+1)^2$. The first one is impossible because
$$
(a+1)^2-b^2=1\Rightarrow(a+1-b)(a+1+b)=1\Rightarrow\begin{cases}
a=0\\
a=-2
\end{cases}
$$
and the second one we get that $a=b^2(b^2+2)$.
I tried some values of $b$ and I suspect that only $b=1$ is the answer but I don't know if it's correct and I don't know how to prove it.
Any help or hints are welcome. Thanks! 
 A: Let $f(x) = x + 1$ and $g(x) = x^2 + 1$. Suppose we have a sequence 
$$(n, n) \leftarrow (a_1, b_1) \leftarrow (a_2, b_2) \leftarrow \cdots \leftarrow (1, 3)$$
for some $n$, so at each step we have either $(a_i, b_i) = (f(a_{i+1}), g(b_{i+1}))$ or $(a_i, b_i) = (g(a_{i+1}), f(b_{i+1}))$ and all $a_i, b_i$ are positive integers (here $(a_0, b_0) = (n, n)$ and $(a_m, b_m) = (1, 3)$). The key is to show that all of the steps leading to $(n, n)$ must be of the same "type", extending the argument you gave.
Case 1: $(n, n) = (f(a_1), g(b_1))$. 
We'll show by induction on $k$ that $(n, n) = (f^k(a_k), g^k(b_k))$ for each $k$. We are given that it holds in the case $k = 1$. Now suppose $(n, n) = (f^k(a_k), g^k(b_k))$ for some $k$. If we had $(a_k, b_k) = (g(a_{k+1}), f(b_{k+1}))$, then this would mean $f^k(g(a_{k+1})) = g^k(f(b_{k+1}))$, hence $a_{k+1}^2 + (k+1) = d^2 + 1$, where $d = g^{k-1}(b_{k+1} + 1)$. Note $g(x) > x^2$, so inductively $g^{k-1}(x) \geq x^{2^{k-1}}$, giving $d \geq (b_{k+1}+1)^{2^{k-1}} \geq 2^{2^{k-1}}$. But then this gives 
$$k = d^2 - a_{k+1}^2 = (d + a_{k+1})(d - a_{k+1}) \geq d + a_{k+1} > d \geq 2^{2^{k-1}}$$
(which is impossible, as you can prove e.g. by induction). Thus we must have $(a_k, b_k) = (f(a_{k+1}), g(a_{k+1}))$, so $(n, n) = (f^{k+1}(a_{k+1}), g^{k+1}(b_{k+1}))$ as desired. 
Case 2: $(n, n) = (g(a_1), f(b_1))$. 
An identical argument to that given in case 1 shows that $(n, n) = (g^k(a_k), f^k(b_k))$ for each $k$.
Thus we've shown that either $(n, n) = (f^m(1), g^m(3))$ or $(n, n) = (g^m(1), f^m(3))$ for some $m \geq 0$. The first case is impossible: another simple inductive argument shows that if $1 \leq x < y$ then $f^m(x) < g^m(y)$ for each $m \geq 0$, hence we must have $f^m(1) < g^m(3)$ for each $m \geq 0$. For the second case, consider the sequence of $(g^m(1), f^m(3))$ for $m \geq 0$: we have $(1, 3), (2, 4), (5, 5), (26, 6), \dots$, and then by the same fact as before, since $g^3(1) > f^3(3)$, we have $g^m(1) > f^m(3)$ for all $m \geq 3$. We conclude that the only pair $(n, n)$ reached from $(1, 3)$ is $\boxed{(5, 5)}$.
