IMO Problem Shortlist

Such a sequence exists for $n=1,2,3,4$ and no other $n$. Since the existence of such a sequence for some $n$ implies the existence of such a sequence for all smaller $n$, it suffices to prove that $n=5$ is not possible and $n=4$ is possible.

Assume first that for $n=5$ there exists a sequence of positive integers $a_1,a_2,\dots ,a_5$ satisfying the conditions $$\begin{array}{rl}& a_2^2+1=\left(a_1+1\right)\left(a_3+1\right),\\ & a_3^2+1=\left(a_2+1\right)\left(a_4+1\right),\\ & a_4^2+1=\left(a_3+1\right)\left(a_5+1\right).\end{array}$$ Assume $a_1$ is odd, then $a_2$ has to be odd as well and as then $a_2^2+1\equiv 2\mathrm{mod}4,a_3$ has to be even. But this is a contradiction, since then the even number $a_2+1$ cannot divide the odd number $a_3^2+1$.

Hence $a_1$ is even. If $a_2$ is odd, $a_3^2+1$ is even (as a multiple of $a_2+1$ ) and hence $a_3$ is odd, too. Similarly we must have $a_4$ odd as well. But then $a_3^2+1$ is a product of two even numbers $\left(a_2+1\right)\left(a_4+1\right)$ and thus is divisible by 4 , which is a contradiction as for odd $a_3$ we have $a_3^2+1\equiv 2\mathrm{mod}4$.

Hence $a_2$ is even. Furthermore $a_3+1$ divides the odd number $a_2^2+1$ and so $a_3$ is even. Similarly, $a_4$ and $a_5$ are even as well.

Now set $x=a_2$ and $y=a_3$. From the given condition we get $(x+1)\mid \left(y^2+1\right)$ and $(y+1)\mid \left(x^2+1\right)$. We will prove that there is no pair of positive even numbers $(x,y)$ satisfying these two conditions, thus yielding a contradiction to the assumption.

Assume there exists a pair ( $x_0,y_0$ ) of positive even numbers satisfying the two conditions $\left(x_0+1\right)\mid \left(y_0^2+1\right)$ and $\left(y_0+1\right)\mid \left(x_0^2+1\right)$. Then one has $\left(x_0+1\right)\mid \left(y_0^2+1+x_0^2-1\right)$, i.e., $\left(x_0+1\right)\mid \left(x_0^2+y_0^2\right)$, and similarly $\left(y_0+1\right)\mid \left(x_0^2+y_0^2\right)$. Any common divisor $d$ of $x_0+1$ and $y_0+1$ must hence also divide the number $\left(x_0^2+1\right)+\left(y_0^2+1\right)-\left(x_0^2+y_0^2\right)=2$. But as $x_0+1$ and $y_0+1$ are both odd, we must have $d=1$. Thus $x_0+1$ and $y_0+1$ are relatively prime and therefore there exists a positive integer $k$ such that $$k(x+1)(y+1)=x^2+y^2$$ has the solution $\left(x_0,y_0\right)$. We will show that the latter equation has no solution $(x,y)$ in positive even numbers.

Assume there is a solution. Pick the solution $\left(x_1,y_1\right)$ with the smallest sum $x_1+y_1$ and assume $x_1\ge y_1$. Then $x_1$ is a solution to the quadratic equation $$x^2-k\left(y_1+1\right)x+y_1^2-k\left(y_1+1\right)=0$$ Let $x_2$ be the second solution, which by Vieta's theorem fulfills $x_1+x_2=k\left(y_1+1\right)$ and $x_1{x}_2=y_1^2-k\left(y_1+1\right)$. If $x_2=0$, the second equation implies $y_1^2=k\left(y_1+1\right)$, which is impossible, as $y_1+1>1$ cannot divide the relatively prime number $y_1^2$. Therefore $x_2\ne 0$.

Also we get $\left(x_1+1\right)\left(x_2+1\right)=x_1{x}_2+x_1+x_2+1=y_1^2+1$ which is odd, and hence $x_2$ must be even and positive. Also we have $x_2+1=\frac{y_1^2+1}{x_1+1}\le \frac{y_1^2+1}{y_1+1}\le y_1\le x_1$. But this means that the pair ( $x^{\prime },y^{\prime }$ ) with $x^{\prime }=y_1$ and $y^{\prime }=x_2$ is another solution of $k(x+1)(y+1)=x^2+y^2$ in even positive numbers with $x^{\prime }+y^{\prime }<x_1+y_1$, a contradiction.

Therefore we must have $n\le 4$. When $n=4$, a possible example of a sequence is $a_1=4,a_2=33,a_3=217$ and $a_4=1384$.

---

Alternative solution.

It is easy to check that for $n=4$ the sequence $a_1=4,a_2=33,a_3=217$ and $a_4=1384$ is possible.

Now assume there is a sequence with $n\ge 5$. Then we have in particular $$\begin{array}{rl}& a_2^2+1=\left(a_1+1\right)\left(a_3+1\right),\\ & a_3^2+1=\left(a_2+1\right)\left(a_4+1\right),\\ & a_4^2+1=\left(a_3+1\right)\left(a_5+1\right).\end{array}$$ Also assume without loss of generality that among all such quintuples $\left(a_1,a_2,a_3,a_4,a_5\right)$ we have chosen one with minimal $a_1$.

One shows quickly the following fact: $$\begin{array}{rl}& \text{ If three positive integers }x,y,z\text{ fulfill }{y}^2+1=(x+1)(z+1)\text{ and if }y\text{ is even, then }\\ & x\text{ and }z\text{ are even as well and either }x<y<z\text{ or }z<y<x\text{ holds. }\end{array}\text{\hspace{1em}(1)}$$ Indeed, the first part is obvious and from $x<y$ we conclude $$z+1=\frac{y^2+1}{x+1}\ge \frac{y^2+1}{y}>y$$ and similarly in the other case.

Now, if $a_3$ was odd, then $\left(a_2+1\right)\left(a_4+1\right)=a_3^2+1\equiv 2\mathrm{mod}4$ would imply that one of $a_2$ or $a_4$ is even, this contradicts (1). Thus $a_3$ and hence also $a_1,a_2,a_4$ and $a_5$ are even. According to (1), one has $a_1<a_2<a_3<a_4<a_5$ or $a_1>a_2>a_3>a_4>a_5$ but due to the minimality of $a_1$ the first series of inequalities must hold.

Consider the identity $$\left(a_3+1\right)\left(a_1+a_3\right)=a_3^2-1+\left(a_1+1\right)\left(a_3+1\right)=a_2^2+a_3^2=a_2^2-1+\left(a_2+1\right)\left(a_4+1\right)=\left(a_2+1\right)\left(a_2+a_4\right).$$ Any common divisor of the two odd numbers $a_2+1$ and $a_3+1$ must also divide ( $a_2+1$ )( $a_4+1)-\left(a_3+1\right)\left(a_3-1\right)=2$, so these numbers are relatively prime. Hence the last identity shows that $a_1+a_3$ must be a multiple of $a_2+1$, i.e. there is an integer $k$ such that $$\begin{array}{c}{a}_1+a_3=k\left(a_2+1\right).\end{array}\text{\hspace{1em}(2)}$$ Now set $a_0=k\left(a_1+1\right)-a_2$. This is an integer and we have $$\begin{array}{rl}\left(a_0+1\right)\left(a_2+1\right)& =k\left(a_1+1\right)\left(a_2+1\right)-\left(a_2-1\right)\left(a_2+1\right)\\ & =\left(a_1+1\right)\left(a_1+a_3\right)-\left(a_1+1\right)\left(a_3+1\right)+2\\ & =\left(a_1+1\right)\left(a_1-1\right)+2=a_1^2+1\end{array}$$ Thus $a_0\ge 0$. If $a_0>0$, then by (1) we would have $a_0<a_1<a_2$ and then the quintuple ( $a_0,a_1,a_2,a_3,a_4$ ) would contradict the minimality of $a_1$.

Hence $a_0=0$, implying $a_2=a_1^2$. But also $a_2=k\left(a_1+1\right)$, which finally contradicts the fact that $a_1+1>1$ is relatively prime to $a_1^2$ and thus cannot be a divisior of this number.

Hence $n\ge 5$ is not possible.