Азиатско-Тихоокеанская математическая олимпиада, 2015 год

Найдите все последовательности $a_0, a_1, a_2, \ldots $, состоящие из натуральных чисел, такие что $a_0 \geqslant 2015$ и при всех натуральных $n\geqslant 1$ выполняются следующие условия:
(i) $a_{n+2}$ делится на $a_n$;
(ii) $|s_{n+1}-(n+1)a_n|=1$, где $s_{n+1} = a_{n+1}-a_n+a_{n-1}-\ldots +(-1)^{n+1}a_0.$ ( Pakawut Jiradilok, Warut Suksompong )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Ответ. Два семейства решений:
$\quad$ (а) $a_n=c(n+2)n!$ для всех $n \geq 1$ и $a_0=c+1$ для некоторого целого $c \geq 2014$;
$\quad$ (б) $a_n=c(n+2)n!$ для всех $n \geq 1$ и $a_0=c-1$ для некоторого целого $c \geq 2016$.
Решение. Пусть $\left\{ {{a}_{n}} \right\}_{n=0}^{\infty }$ — последовательность натуральных чисел, удовлетворяющая указанным условиям. Можно переписать (ii) как ${{s}_{n+1}}=(n+1){{a}_{n}}+{{h}_{n}}$, где ${{h}_{n}}\in \left\{ -1,1 \right\}$. Заменяя $n$ на $n-1$, получаем ${{s}_{n}}=n{{a}_{n-1}}+{{h}_{n-1}}$, где ${{h}_{n-1}}\in \left\{ -1,1 \right\}$. Заметим, что $a_{n+1} = s_{n+1} + s_n$, поэтому существует такое $\delta_n \in \{-2,0,2 \}$, что \[{{a}_{n+1}}=(n+1){{a}_{n}}+n{{a}_{n-1}}+{{\delta }_{n}}. \quad (1)\] Также имеем: $|{{s}_{2}}-2{{a}_{1}}|=1$, что приводит к ${{a}_{0}}=3{{a}_{1}}-{{a}_{2}}\pm 1\le 3{{a}_{1}}$, следовательно, ${{a}_{1}}\ge \frac{{{a}_{0}}}{3}\ge 671$. Подставляя $n=2$ в (1), находим: ${{a}_{3}}=3{{a}_{2}}+2{{a}_{1}}+{{\delta }_{2}}$. Поскольку ${{a}_{1}}|{{a}_{3}}$, то ${{a}_{1}}|3{{a}_{2}}+{{\delta }_{2}}$, откуда ${{a}_{2}}\ge 223$. Используя (1), получаем, что ${{a}_{n}}\ge 223$ для всех $n\ge 0$.
$\quad$Лемма. Для $n\ge 4$ справедливо соотношение ${{a}_{n+2}}=(n+1)(n+4){{a}_{n}}.$
$\quad$Доказательство. Если $n\ge 3$, то $${{a}_{n}}=n{{a}_{n-1}}+(n-1){{a}_{n-2}}+{{\delta }_{n-1}} > n{{a}_{n-1}}+3. \quad (2)$$ Используя (2) и заменяя $n$ на $n-1$, имеем, что для $n\ge 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}}. \quad (3)$$ В силу (1) мы можем переписать ${{a}_{n+2}}$ в терминах ${{a}_{n}}$ и ${{a}_{n-1}}$, что вместе с (2) дает следующее соотношение для $n\ge 3$: $${{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) < ({{n}^{2}}+5n+5){{a}_{n}}.$$ К тому же, для $n\ge 4$: $$ {{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}} =({{n}^{2}}+5n+3){{a}_{n}}. $$ Поскольку ${{a}_{n}}|{{a}_{n+2}}$, имеем: ${{a}_{n+2}}=({{n}^{2}}+5n+4){{a}_{n}}=(n+1)(n+4){{a}_{n}}$, что и требовалось доказать.
$\quad$Лемма 2. При $n\ge 4$ справедливо соотношение $${{a}_{n+1}}=\frac{(n+1)(n+3)}{n+2}{{a}_{n}}.$$
$\quad$Доказательство. Используя рекуррентное соотношение $${{a}_{n+3}}=(n+3){{a}_{n+2}}+(n+2){{a}_{n+1}}+{{\delta }_{n+2}}$$ и, переписывая ${{a}_{n+3}}$, ${{a}_{n+2}}$ в терминах ${{a}_{n+1}}$, ${{a}_{n}}$, согласно лемме 1, получаем: $$(n+2)(n+4){{a}_{n+1}}=(n+3)(n+1)(n+4){{a}_{n}}+{{\delta }_{n+2}}.$$ Следовательно, $n+4|{{\delta }_{n+2}}$, что приводит к ${{\delta }_{n+2}}=0$ и $${{a}_{n+1}}=\frac{(n+1)(n+3)}{n+2}{{a}_{n}},$$ что и требовалось доказать. Предположим, что существует такое $n\ge 1$, что $${{a}_{n+1}}\ne \frac{(n+1)(n+3)}{n+2}{{a}_{n}}.$$ Согласно лемме 2, существует наибольшее $1\le m\le 3$ с этим условием. Тогда ${{a}_{m+2}}=\frac{(m+2)(m+4)}{m+3}{{a}_{m+1}}$. Если ${{\delta }_{m+1}}=0$, то $${{a}_{m+1}}=\frac{(m+1)(m+3)}{m+2}{{a}_{m}},$$ что противоречит выбору $m$. Значит, ${{\delta }_{m+1}}\ne 0$. Ясно, что $m+3|{{a}_{m+1}}$. Положим ${{a}_{m+1}}=(m+3)k$ и ${{a}_{m+2}}={(m+2)}\cdot{(m+4)k}$. Тогда $$(m+1){{a}_{m}}+{{\delta }_{m+1}}={{a}_{m+2}}-(m+2){{a}_{m+1}}=(m+2)k.$$ Таким образом, ${{a}_{m}}|(m+2)k-{{\delta }_{m+1}}$. Но ${{a}_{m}}$ также делит ${{a}_{m+2}}={(m+2)}{(m+4)k}$. Отсюда ${{a}_{m}}|{(m+4)}{{\delta }_{m+1}}$. Поскольку ${{\delta }_{m+1}}\ne 0$, имеем: ${{a}_{m}}|{2m+8}\le 14$, что противоречит предыдущему результату о том, что ${{a}_{n}}\ge 223$ для всех неотрицательных $n$. Итак, ${{a}_{n+1}}=\frac{(n+1)(n+3)}{n+2}{{a}_{n}}$ при всех $n\ge 1$. Подставляя $n=1$, получаем, что $3|{{a}_{1}}$. Полагая ${{a}_{1}}=3c$, по индукции находим, что ${{a}_{n}}=n!(n+2)c$ для $n\ge 1$. Поскольку $|{{s}_{2}}-2{{a}_{1}}|=1$, то ${{a}_{0}}=c\pm 1$, что дает два семейства решений. Замечая, что $(n+2)n!=n!+(n+1)!$, находим: ${{s}_{n+1}}=c(n+2)!+{{(-1)}^{n}}(c-{{a}_{0}})$. Следовательно, оба семейства решений удовлетворяют условиям задачи.