Cesko-Slovacko-Poljsko 2006

Every sequence satisfying given conditions is determined by first two terms. Thus we are looking for integer pairs $(a_1,a_2)$, for which all the other terms are integers. Writing out the formula for several small values of $n$ and multiplying it we obtain $$\begin{array}{rl}{a}_3(a_2+1)& =a_1+2006,\\ a_4(a_3+1)& =a_2+2006,\\ a_5(a_4+1)& =a_3+2006,\end{array}$$ Subtracting adjacent equalities (to remove number 2006) and rearranging gives $$\begin{array}{rl}{a}_3-a_1& =(a_3+1)(a_4-a_2),\\ a_4-a_2& =(a_4+1)(a_5-a_3),\\ a_5-a_3& =(a_5+1)(a_6-a_4),\end{array}\text{\hspace{1em}(1)}$$

All the terms $(a_n+1)$ are nonzero by definition. Hence two possibilities can happen. If $a_3-a_1=0$, by substituting into previous we get (step by step) $a_4-a_2=0$, $a_5-a_3=0$, ..., i.e. $$a_1=a_3=a_5=\dots \text{and}{a}_2=a_4=a_6=\dots (2)$$ On the other side, if $a_3-a_1\ne 0$, by the same substituting we obtain $a_4-a_2\ne 0$, $a_5-a_3\ne 0$, ... First have a look at the second case. By (1) we have $$0<|a_{n+3}-a_{n+1}|=|a_{n+2}-a_n|\cdot \frac{1}{|a_{n+2}+1|}\le |a_{n+2}-a_n|(3)$$ for all $n\ge 1$. Thus we have non-increasing sequence of positive integers $$|a_3-a_1|\ge |a_4-a_2|\ge |a_5-a_3|\ge \dots$$ Obviously this sequence is constant after some term (otherwise we could select infinite decreasing subsequence of positive integers, which is anyway impossible). Thus there is some index $N$ and value $d$ with $|a_{n+2}-a_n|=d$ for all $n\ge N$. By (3) then $|a_{n+2}+1|=1$, i.e. for $n\ge N+2$ we have $a_n\in \{0,-2\}$. But by definition $$a_{N+4}=\frac{a_{N+2}+2006}{a_{N+3}+1},$$ hence $a_{N+4}$ is one of the values $$\frac{0+2006}{0+1}=2006,\frac{0+2006}{-2+1}=-2006,\frac{-2+2006}{0+1}=2004,\frac{-2+2006}{-2+1}=-2004.$$ This is in contrary with $a_{N+4}\in \{0,-2\}$. In this case there is no sequence satisfying given conditions. Therefore every such sequence satisfies (2). Substituting $n=1$ and $a_3=a_1$ in definition we get $$a_1=\frac{a_1+2006}{a_2+1}\text{or}{a}_1{a}_2=2006=2\cdot 17\cdot 59.$$ Considering $a_1,a_2\ne -1$ we obtain $$a_1\in \{1,\pm 2,\pm 17,\pm 34,\pm 59,\pm 118,\pm 1003,2006\}\text{and}{a}_2=\frac{2006}{a_1}.$$ It can be easily verified every such sequence $a_1,a_2,a_3,a_4,a_5,\dots$ satisfies given condition. The number of sequences is 14.