Asian Pacific Mathematics Olympiad

There are two families of answers: (a) $a_{n}=c(n+2) n$ ! for all $n \geq 1$ and $a_{0}=c+1$ for some integer $c \geq 2014$, and (b) $a_{n}=c(n+2) n$ ! for all $n \geq 1$ and $a_{0}=c-1$ for some integer $c \geq 2016$. Let $\left\{a_{n}\right\}_{n=0}^{\infty}$ be a sequence of positive integers satisfying the given conditions. We can rewrite (ii) as $s_{n+1}=(n+1) a_{n}+h_{n}$, where $h_{n} \in\{-1,1\}$. Substituting $n$ with $n-1$ yields $s_{n}=n a_{n-1}+h_{n-1}$, where $h_{n-1} \in\{-1,1\}$. Note that $a_{n+1}=s_{n+1}+s_{n}$, therefore there exists $\delta_{n} \in\{-2,0,2\}$ such that $$a_{n+1}=(n+1) a_{n}+n a_{n-1}+\delta_{n}$$ We also have $\left|s_{2}-2 a_{1}\right|=1$, which yields $a_{0}=3 a_{1}-a_{2} \pm 1 \leq 3 a_{1}$, and therefore $a_{1} \geq \frac{a_{0}}{3} \geq 671$. Substituting $n=2$ in (1), we find that $a_{3}=3 a_{2}+2 a_{1}+\delta_{2}$. Since $a_{1} \mid a_{3}$, we have $a_{1} \mid 3 a_{2}+\delta_{2}$, and therefore $a_{2} \geq 223$. Using (1), we obtain that $a_{n} \geq 223$ for all $n \geq 0$. Lemma 1: For $n \geq 4$, we have $a_{n+2}=(n+1)(n+4) a_{n}$. Proof. For $n \geq 3$ we have $$a_{n}=n a_{n-1}+(n-1) a_{n-2}+\delta_{n-1}>n a_{n-1}+3$$ By applying (2) with $n$ substituted by $n-1$ we have for $n \geq 4$, $$a_{n}=n a_{n-1}+(n-1) a_{n-2}+\delta_{n-1}<n a_{n-1}+(a_{n-1}-3)+\delta_{n-1}<(n+1) a_{n-1}$$ Using (1) to write $a_{n+2}$ in terms of $a_{n}$ and $a_{n-1}$ along with (2), we obtain that for $n \geq 3$, $$\begin{aligned} a_{n+2} & =(n+3)(n+1) a_{n}+(n+2) n a_{n-1}+(n+2) \delta_{n}+\delta_{n+1} \\ & <(n+3)(n+1) a_{n}+(n+2) n a_{n-1}+3(n+2) \\ & <\left(n^{2}+5 n+5\right) a_{n} . \end{aligned}$$ Also for $n \geq 4$, $$\begin{aligned} a_{n+2} & =(n+3)(n+1) a_{n}+(n+2) n a_{n-1}+(n+2) \delta_{n}+\delta_{n+1} \\ & >(n+3)(n+1) a_{n}+n a_{n} \\ & =\left(n^{2}+5 n+3\right) a_{n} . \end{aligned}$$ Since $a_{n} \mid a_{n+2}$, we obtain that $a_{n+2}=\left(n^{2}+5 n+4\right) a_{n}=(n+1)(n+4) a_{n}$, as desired. Lemma 2: For $n \geq 4$, we have $a_{n+1}=\frac{(n+1)(n+3)}{n+2} a_{n}$. Proof. Using the recurrence $a_{n+3}=(n+3) a_{n+2}+(n+2) a_{n+1}+\delta_{n+2}$ and writing $a_{n+3}$, $a_{n+2}$ in terms of $a_{n+1}, a_{n}$ according to Lemma 1 we obtain $$(n+2)(n+4) a_{n+1}=(n+3)(n+1)(n+4) a_{n}+\delta_{n+2}$$ Hence $n+4 \mid \delta_{n+2}$, which yields $\delta_{n+2}=0$ and $a_{n+1}=\frac{(n+1)(n+3)}{n+2} a_{n}$, as desired. Suppose there exists $n \geq 1$ such that $a_{n+1} \neq \frac{(n+1)(n+3)}{n+2} a_{n}$. By Lemma 2, there exist a greatest integer $1 \leq m \leq 3$ with this property. Then $a_{m+2}=\frac{(m+2)(m+4)}{m+3} a_{m+1}$. If $\delta_{m+1}=0$, we have $a_{m+1}=\frac{(m+1)(m+3)}{m+2} a_{m}$, which contradicts our choice of $m$. Thus $\delta_{m+1} \neq 0$. Clearly $m+3 \mid a_{m+1}$. Write $a_{m+1}=(m+3) k$ and $a_{m+2}=(m+2)(m+4) k$. Then $(m+$ 1) $a_{m}+\delta_{m+1}=a_{m+2}-(m+2) a_{m+1}=(m+2) k$. So, $a_{m} \mid(m+2) k-\delta_{m+1}$. But $a_{m}$ also divides $a_{m+2}=(m+2)(m+4) k$. Combining the two divisibility conditions, we obtain $a_{m} \mid(m+4) \delta_{m+1}$. Since $\delta_{m+1} \neq 0$, we have $a_{m} \mid 2 m+8 \leq 14$, which contradicts the previous result that $a_{n} \geq 223$ for all nonnegative integers $n$. So, $a_{n+1}=\frac{(n+1)(n+3)}{n+2} a_{n}$ for $n \geq 1$. Substituting $n=1$ yields $3 \mid a_{1}$. Letting $a_{1}=3 c$, we have by induction that $a_{n}=n!(n+2) c$ for $n \geq 1$. Since $\left|s_{2}-2 a_{1}\right|=1$, we then get $a_{0}=c \pm 1$, yielding the two families of solutions. By noting that $(n+2) n!=n!+(n+1)!$, we have $s_{n+1}=c(n+2)!+(-1)^{n}\left(c-a_{0}\right)$. Hence both families of solutions satisfy the given conditions.