Potla wrote: Let $P(x)=x+1$ and $Q(x)=x^2+1.$ Consider all sequences $\langle(x_k,y_k)\rangle_{k\in\mathbb{N}}$ 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))$ for each $k. $ We say that a positive integer $n$ is nice if $x_n=y_n$ holds in at least one of these sequences. Find all nice numbers. (1,3), (4,2),(5,5) 3 is nice.

Click to reveal hidden text

Anyone for this? I couldn't get anything...

Below is a solution, that looks good to me, and showing, $n=3$ is the only nice number. For $n=3$, the following way, $(1,3)\to (2,4)\to (5,5)$ is an answer. Clearly, $n=2$ and $n=1$ cannot be an answer. We claim that there are no more $n$'s. The approach is as follows. We suppose that $n\geq 4$. Case 1: $x_n = Q(x_{n-1})$, $y_n =P(y_{n-1})$. In this case, $$ x_{n-1}^2 + 1 =y_{n-1}+1 \implies \exists a: (x_{n-1},y_{n-1})=(a,a^2). $$Since, $x_{n-1}\geq x_{1}+(n-2)\implies a\geq n-1\geq 3$. Now, we claim that, $y_{n-1}=P(y_{n-2})$ (in fact, for a 'very long time', which will be the key idea of the argument). Suppose that, $y_{n-1}=Q(y_{n-2})=y_{n-2}^2 +1$. Hence, $$ (a-y_{n-2})(a+y_{n-2})=1 \implies a=1,y_{n-2}=0, $$contradiction. Therefore, $y_{n-1}=P(y_{n-2})=y_{n-2}+1$, and, $x_{n-1}=Q(x_{n-2})=x_{n-2}^2+1$. Namely, $(n-2)^{th}$ step can be written as, $$ (x_{n-2},y_{n-2})=\left(\sqrt{a-1},a^2-1\right). $$Clearly, $\sqrt{a-1}>1$, and thus, $a=t^2+1$, for some $t\geq 2$ (since $a\geq 3$, $t\geq 2$ must hold). Rewriting the pair, in terms of $t$, yields, $$ (x_{n-2},y_{n-2})=\left(t,(t^2+1)^2-1\right),\quad \exists t\geq 2. $$Now, we further claim that, $y_{n-2}=P(y_{n-3})$. To see this, note that, had it been otherwise, we would have had, $$ (t^2+1)^2-2 = y_{n-3}^2 \implies \left(t^2+1-y_{n-3}\right)\left(t^2+1+y_{n-3}\right)=2, $$which is impossible, since, the only factorization is $t^2+1-y_{n-3}=1$ and $t^2+1-y_{n-3}=2$, however, these two terms differ by an even number ($2y_{n-3}$), while, $2-1$ is odd. Let us now estimate, how far we have the scenario, $y_{i}=P(y_{i-1})$. Notice that, $y_i = Q(y_{i-1})$ may hold, only if, $y_i-1$ is a square. So, our approach will be to estimate, how much $y_i-1$ is off, by the previous perfect square; and at each step, update the estimate, and show that, this grows, hence, will be giving that, the only way to obtain $(x_n,y_n)$ is to apply only $Q$ to the first coordinate, and only $P$ to the second coordinate, namely, $$ (x_n,y_n)=(Q^{(n-1)}(1),P^{n-1}(1)), $$and, can be shown to be impossible (through very basic estimates on how these terms grow). Coming back to where we have left off, note, $$ y_{n-3}+1 = y_{n-2}=(t^2+1)^2 -1 \implies y_{n-3}=(t^2+1)^2 - 2. $$Hence, $$ (x_{n-3},y_{n-3})=\left(\sqrt{t-1},(t^2+1)^2 - 2\right)=\left(\sqrt{t-1},t^4+2t^2-1\right)\hspace{0.1in} \exists t\geq 2. $$Quick observation, yields, $(t^2)^2 < t^4+2t^2 -2 < (t^2+1)^2$, hence, the next square is $t^4$. Thus, until we hit this, we have to keep applying $P$ to second coordinate. Note that, if we need $\alpha$ iterations, then, $t^4+2t^2 - 2 -\alpha=t^4$ giving us, we need, at the very least, $2t^2-2$ iterations. Since, $t\geq 2$, this means, we need at least $6$ more iterations. Now, clearly, $t=2$ is not a solution for above, hence, $t-1=a^2$, for some $a \geq 2$. Therefore, the previous step can be written as, $$ (x_{n-3},y_{n-3})=\left(a,\left(\left(a^2+1\right)^2+1\right)^2-2\right), \hspace{0.1in} \exists a\geq 2. $$This update on $a$ gives us, $t\geq 5$, hence, $2\times 5^2 -2 -1=47$ more iterations are required (mainly, $2t^2-1-1$, with the updated estimate on $t$). Next, with this, $$ (x_{n-4},y_{n-4})=\left(\sqrt{a-1},\left(\left(a^2+1\right)^2+1\right)^2-2\right),\hspace{0.1in} \exists a\geq 2. $$Now, $a-1 = u^2$, for some $u$. Since, $a\neq 2$ (obvious), $u\geq 2$, and thus, $a\geq 5$. If $a\geq 5$, then, $t\geq 26$, hence, the required updates now goes up to, $$ 2t^2-3 = 2\times 26^2 - 2 = \text{ LARGE }. $$With this approach, we see that, at some place, since, the first coordinate is decreasing at a faster rate, it must hit $1$, while, for this, the second coordinate will be too much off, hence, not possible. Case 2:This is, almost the same argument. Just suppose, this time, that $(x_{n-1},y_{n-1})=(a^2,a)$. Clearly, $a\geq 2$. Therefore, $(x_{n-2},y_{n-2})=(a^2-1,\sqrt{a-1})$. Now, $\sqrt{a-1}\in\mathbb{N}$. Hence, $a=t^2+1$ for some $t$. Also note, $t\geq 2$, since, $a=2$ is not a solution. Hence, $$ (x_{n-2},y_{n-2})=((t^2+1)^2-1,t),\hspace{0.1in} t\geq 2, $$therefore, $$ (x_{n-3},y_{n-3})=((t^2+1)^2-2,\sqrt{t-1}) \implies \sqrt{t-1}\in\mathbb{N} \implies t=u^2+1,u\geq 2, $$and thus, $$ (x_{n-3},y_{n-3})=\left(\left(\left(u^2+1\right)^2+1\right)^2-2,u\right), \hspace{0.1in}, \exists u\geq 2. $$It is easy to see that, we enter into the same loop, and, can never reach to $(1,3)$. We are done.