Let $b_k=a_{k-1}-a_k$, then ${b_{k+1}=\frac{(b_k+2)a_k+b_k}{a_k+b_k+1}<b_k+2}$. Therefore if $a_1=N^2,a_2=N^2-1$, then $a_3>N^2-2^2,a_4>N^2-3^2,...a_{N+1}>N^2-N^2=0.$

This is like a "troll" problem. Very simple, but it is stated in such a way that it tricks you into trying other stuff that doesn't work. The answer is $4$. It is easy to see that if there were $5$, then we would have two even distinct numbers $n$ and $m$ (either $a_2$ and $a_3$ or $a_3$ and $a_4$) satisfying $n+1 | m^2+1$ and $m+1 | n^2+1$. But this is impossible. To prove this, take the least two such numbers $n$ and $m$ (with $n+m$ minimal), and take $m'=(n^2+1)/(m+1)-1$, with $m \textgreater n$. It is easy to see $(n,m')$ also satisfies and that $m' \textless m$. So we must have $m'=0$ so $n^2+1=m+1$ so $n^2=m$, which is easy to discard. So the answer must be at most $4$. To find such a sequence of 4, one must prove a nontrivial ($n^2 \neq m \neq \sqrt{n}$, $n,m \ge 3$) solution to $n+1 | m^2+1$ and $m+1 | n^2+1$ (where they are both odd), exists. I initially thought they didn't exist. Later I did some casework and found a solution. The smallest such solution is $33$, $217$. I doubt the problem requires you to find this value, so I guess there's an easier way to prove these numbers exist.

The answer is $n\le 4$, which is achievable with the sequence $4,33,217,1384$. First, suppose that $a_i$ is odd. Then, we need $2|a_{i+1}^2+1$, so $a_{i+1}\equiv 1\pmod 2$. So, an odd number must follow an odd number. However, $a_{i+1}^2+1\equiv 2\pmod 4$, so $\frac{a_{i+1}^2+1}{a_i+1}\equiv 1\pmod 2\implies 2|a_{i+2}$. Therefore, $a_{i+3}$ cannot exist. So, if $a_i$ is an odd, then $n\le i+2$. Suppose, then, that $2|a_1,a_2$. Then, we need $a_1+1|a_2^2+1$, and $$a_2+1|a_3^2+1=\left(\frac{a_2^2-a_1}{a_1+1}\right)^2+1\implies a_2+1\bigg|a_2^4-2a_2^2a_1+2a_1^2+2a_1+1\implies a_2+1|2a_1^2+2\implies a_2+1|a_1^2+2$$So, we have two even numbers such that $a+1|b^2+1,b+1|a^2+1$. I claim that no such pair exists, which we can do with Vieta Jumping. Suppose there exists such $a,b$, and consider the pair which minimizes $a+b$. Also, WLOG $b\le a$ and define $k=\frac{b^2+1}{a+1}-1$. Of course, $k\in2\mathbb{Z}^+$, since if $a=b^2$, then $b+1|b^4+1\iff b+1|2$, which is a contradiction. Furthermore, $k=\frac{b^2-a}{a+1}<\frac{a^2+a}{a+1}=a$, and $$k^2+1=\left(\frac{b^2-a}{a+1}\right)^2+1=\frac{b^4-2b^2a+2a^2+2a+1}{(a+1)^2}=\frac{(b+1)(b^3-b^2+(2-2a)b+(2a-2))+2(a^2+1)}{(a+1)^2}$$As $\gcd(b+1,a+1)|\gcd(b+1,b^2+1)=1$ and $b+1|a^2+1$, we must have that $b+1|k^2+1$. So, $(k,b)$ satisfies our conditions, and $k<a$, so minimality is contradicted. Therefore, if $2|a_{k-1},a_k$, then $a_{k+1}$ cannot exist. Given these restrictions, our sequence can start like: OE, OOE, EE, EOE, EOOE, giving it a maximum length of 4, as desired.

Solved with goodbear, Th3Numb3rThr33. The answer is \(n\le4\), achieved by \(4\), \(33\), \(217\), \(1384\). First observe that \(a_{k-1}\) odd and \(a_k\) even imply \(a_{k+1}\) does not exist; \(a_{k-1}\) odd and \(a_k\) odd imply \(a_{k+1}\) even; \(a_{k-1}\) even and \(a_k\) odd imply \(a_{k+1}\) odd. \(a_{k-1}\) even and \(a_k\) even imply \(a_{k+1}\) even. Hence unless the sequence is forever even, its maximum length is four. Lemma: If \(a\), \(b\) are even, then \(a+1\mid b^2+1\) and \(b+1\mid a^2+1\) cannot simultaneously hold. Proof. The proof is Vieta jumping: take the minimal pair \((a,b)\), and let \[\frac{b^2+1}{a+1}=m+1\quad\text{and}\quad\frac{a^2+1}{b+1}=n+1.\]We cannot simultaneously have \(m\ge a\) and \(n\ge b\), so without loss of generality \(m<a\). Note \(\gcd(a,b+1)=\gcd(a+1,b+1)=1\) since \(b+1\mid a^2+1\), \(a\mid a^2\), \(a+1\mid a^2-1\). By design, \(m+1\mid b^2+1\) and \[m^2+1\equiv\left(\frac{b^2+1}{a+1}-1\right)^2+1\equiv\left(\frac{1-a}{1+a}\right)^2+1\equiv\frac{-2a}{2a}+1\equiv0\pmod{b+1},\]so \((m,b)\) is a smaller pair that works. \(\blacksquare\) But if the sequence is all even and has length at least four, then both \(a_2+1\mid a_3^2+1\) and \(a_3+1\mid a_2^2+1\) hold, contradiction.

The answer is $n=3$ and $n=4$. Notice that by taking $(a_1,a_2,a_3,a_4)=(4,33,217,1384)$, the condition is satisfied. Now notice that if such sequence exists for $n$ then we can simply take its first $m(m<n)$ terms to form a sequence with $m$ terms. Hence it suffices to show that there does not exist such a sequence for $n=5$. Suppose on the contrary that such a sequence exists for $n=5$. CLAIM 1. Both $a_1$ and $a_2$ are even Proof. This is just simple case work. We call an integer $i$ bad if $a_i$ is odd and $a_{i+1}$ is even. Notice that if $1\leq i\leq 3$ is bad, then $$a_{i+2}=\frac{a_{i+1}^2+1}{a_i+1}-1$$can not be an integer since $a_{i+1}^2+1$ is odd while $a_i+1$ is even, contradiction. Now 1. If $a_1$ is odd while $a_2$ is even then $1$ is bad, contradiction. 2. If both $a_1$ and $a_2$ is odd then $a_3$ is even, hence $2$ is bad, contradiction. 3. If $a_1$ is even while $a_2$ is odd then it is easy to see that $a_3$ is odd. Now notice that $$a_4=\frac{a_3^2+1}{a_2+1}-1$$Notice that $a_3^2+1\equiv 2\pmod 4$. Hence $a_4$ is even. This implies that $3$ is bad, contradiciton. This justifies the claim. CLAIM 2. $a_2+1|(a_1^2+1)$ Proof. Let $k=a_1+1$. We first show that $(k,a_2+1)=1$. Indeed if $p|k$ and $p|a_2+1$, from $a_1+1|a_2^2+1$ we have $$0\equiv a_2^2+1\equiv (-1)^2+1\equiv 2\pmod p$$Hence $p=2$. But from CLAIM 1 we show that $k$ is odd, contradiction. Therefore, the inverse of $k$ modulo $a_2+1$ exists. Now using $a_3=\frac{a_2^2+1}{a_1+1}$ we obtain \begin{align*} 0&\equiv a_3^2+1\\ &\equiv ((-1)^2+1)k^{-1}-1)^2+1\\ &\equiv 4k^{-2}-4k^{-1}+2\\ &\equiv 4k^{-2}(1-k)+2\pmod{a_2+1} \end{align*}Hence \begin{align*} 4k^{-2}(k-1)&\equiv 2\pmod{a_2+1}\\ 4(k-1)&\equiv 2k^2\pmod{a_2+1}\\ 2((k-1)^2+1)&\equiv 0\pmod{a_2+1}\\ a_1^2+1&\equiv 0\pmod{a_2+1} \end{align*}since $a_2+1$ is odd. Now let $x=a_1+1$ and $y=a_2+1$. Then $(x,y)$ satisfies the system $$x|(y-1)^2+1$$$$y|(x-1)^2+1$$Since $(x,y)=1$ we have \begin{align} xy|(x+y-1)^2+1 \end{align}CLAIM 3. The only positive integer solution to $(1)$ is $(1,1)$. Proof. We will use the infinite descent method. WLOG assume $x\geq y$.Suppose that there exists another solution to $(1)$ other than $(1,1)$. We pick the one such that $x$ is minimized. Notice that $$(x+y-1)^2+1\equiv (x-1)^2+(y-1)^2\pmod xy$$Hence we have $$kxy=(x-1)^2+(y-1)^2$$for some $k\in\mathbb N$. Now since this is an quadratic equation in $x$ there exists another root $x'$ which satisfies \begin{align*} x+x'&=2+ky\\ xx'&=(y-1)^2+1\\ \end{align*}From these we see that $x'$ is a positive integer. Moreover $$x'=\frac{(y-1)^2+1}{x}\leq\frac{(x-1)^2+1}{x}<x$$From the minimality of $x$ we have $x'=1$. Hence $y=1$. From $(1)$ we have $x=1$, contradiciton. Therefore we must have $a_1=a_2=0$, contradiction.

There are no $(m,n)\in (2\mathbb N)^2$ such that $m+1\mid n^2+1$ and $n+1\mid m^2+1$. Suppose there exists with $m+n$ minimal and $WLOG: m>n$. Notice $$(m+1)(n+1)\mid m^2+n^2$$So indeed $m^2+n^2=kmn+km+kn+k$ for some positive integer $k$. So $$m^2-(kn+k)m+n^2-kn-k=0$$Let $m_0$ be the other root. It follows $m+m_0=k(n+1)$ and $mm_0+k(n+1)=n^2<m^2\implies m_0<m$. By $m+n$ minimal we get that if $m_0\in\mathbb N$ this implies $m_0$ is odd. But so $0\equiv n^2\equiv mm_0+m+m_0\mod 4$ indeed $mm_0\equiv -(m+m_0)\mod 4$ but we have an odd part in $RHS$ and even in $LHS$ contradiction indeed $m_0\in\mathbb Z^-$. So it follows $mm_0+m+m_0=n^2>0$ so $mm_0>-(m+m_0)$ which is a clearly contradiction since $|mm_0|>|m+m_0|$. Note: This solution works if $\gcd(m+1,n+1)=1$.

I proved that $n\geq 5$ fails, and I got stuck on $n=4$ case. I tried to prove that "There is not odd $a,b$ such that \(a+1\mid b^2+1\) and \(b+1\mid a^2+1\)". But I coldn't prove it, because it is not true. So I want to know the motivaton behind finiding example for $n=4$, because to find it you need to check numbers, but there are a lot of numbers until valid one.

Jalil_Huseynov wrote: I proved that $n\geq 5$ fails, and I got stuck on $n=4$ case. I tried to prove that "There is not odd $a,b$ such that \(a+1\mid b^2+1\) and \(b+1\mid a^2+1\)". But I coldn't prove it, because it is not true. So I want to know the motivaton behind finiding example for $n=4$, because to find it you need to check numbers, but there are a lot of numbers until valid one. https://www.imo-official.org/problems/IMO2009SL.pdf See Comment 1

It is not possible for $n\ge 5$. If it were possible then $(a_1+1)(a_3+1)=a^2+1$, $(a_2+1)(a_4+1)=a^3+1$, and $(a_3+1)(a_5+1)=a^4+1$. Note that in the equation $(x+1)(z+1)=y^2+1$, if $x$ and $z$ were both odd then $4\mid y^2+1$ which is impossible. Furthermore, if $x$ or $z$ were odd then $y$ is odd. If $x$ and $z$ are even then $y$ is even. We know that of $a_2$ or $a_4$, one is even, so $a_3$ must be also even. WLOG, $a_2$ is even with $a_3$. Then, we have $a_2+1\mid a_3^2+1$ and $a_3+1\mid a_2^2+1$ and both are even. We prove that no such pair $(a_2,a_3)$ can exist. Suppose it does exist then select the minimal pair $(a,b)$. If $a=b$ then $a+1\mid a^2+1$ which implies $a=1$, so WLOG let $a>b$. Let $(a+1)(c+1)=b^2+1$. Since $a>b$, we have $c<b$. We already know that $c+1\mid b^2+1$. We'll show that $(c,b)$ is a smaller pair by looking at $c^2+1\pmod {b+1}$. Note that $b^2\equiv 1\pmod {b+1}$. We have \[c^2+1=\left(\frac{b^2+1}{a+1}-1\right)^2+1\equiv\left(\frac{a-1}{a+1}\right)^2+1\equiv\frac{a^2-2a+1}{a^2+2a+1}+1\pmod{b+1}\]but since $a^2\equiv -1\pmod {b+1}$ we have that this is equivalent to $0$ so we constructed a smaller pair. Since $c$ must also be even, this is a contradiction. For $n\le 4$ consider the sequence: $12,57,249,1068$.