　数列 $\\{a_n\\} , \\{b_n\\}$ は以下の漸化式によって定まり，特に任意の非負整数 $n$ に対して $b_n-a_n \gt 0$ であることを数学的帰納法で示そう．
$$
\begin{cases}
a_0 = 1\\\\
b_0 = 3
\end{cases}
,\quad 
\begin{cases}
a_{n} = (b_{n-1}-a_{n-1})(2^{n-1}+3) -b_{n-1}\\\\
b_{n} = (b_{n-1}-a_{n-1})(2^{n}+3) -a_{n-1}
\end{cases}
\quad (n\geq 1)
$$

- $n=0$ のでの成立は容易に確かめられる．
- ある非負整数 $n$ までにおいて，上記の成立を仮定する．このとき $a_{n+1}, b_{n+1}$ がはじめの漸化式のように $a_n, b_n$ によって表され，かつ $b_{n+1} - a_{n+1} \gt 0$ を満たしていることを示す．\
$2^{n+1}+3$ と $2^n+3$ が互いに素であることから，$x,y$ はある整数 $k$ を用いて
$$
\begin{cases}
x=k(2^{n}+3) -b_{n}\\\\
y=k(2^{n+1}+3) -a_{n}
\end{cases}
$$
と表すことができる．$y$ を最大化するためには，$k$ を最大化すればよい．ここで，$2$ つめの条件に現れる分数については
$$
\begin{aligned}
\dfrac{b_{n}+y}{a_{n}+x} 
&= \dfrac{k(2^{n+1}+3)+b_{n}-a_{n}}{k(2^{n}+3)-(b_{n}-a_{n})}\\\\
&= \dfrac{2^{n+1}+3}{2^{n}+3} + \dfrac{2^{n+1}+2^{n}+6}{2^{n}+3} \cdot \dfrac{b_{n}-a_{n}}{k(2^{n}+3)-(b_{n}-a_{n})}
\end{aligned}
$$
と表すことができる．仮定より $b_n-a_n \gt 0$ であることを踏まえれば， 
$$
k\gt \dfrac{b_{n}-a_{n}}{2^{n}+3} \tag{1}
$$
のもとでは，この値が $k$ に関して単調に減少し，その収束値は $1 \lt \dfrac{2^{n+1}+3}{2^{n}+3} \lt 2$ である．したがって，これが整数であるならば
$$
\dfrac{k(2^{n+1}+3)+b_{n}-a_{n}}{k(2^{n}+3)-(b_{n}-a_{n})} \geq 2
$$
である．この不等式を整理することで $b_{n}-a_{n} \geq k$ を得る．逆に $k=b_{n}-a_{n}$ としたときに $x,y$ は問題の条件および $ (1)$ の不等式を満たしている．以上より，$k$ の最大値は $b_{n}-a_{n}$ であるから
$$
\begin{cases}
a_{n+1}=(b_{n}-a_{n})(2^{n}+3) -b_{n}\\\\
b_{n+1}=(b_{n}-a_{n})(2^{n+1}+3) -a_{n}
\end{cases}
$$
と確定させることができ，これは当初の漸化式の通りである．ここで，第2式から第1式を差し引くと
$$
b_{n+1} - a_{n+1} = (2^{n}+1) (b_{n} - a_{n}) \tag{2}
$$
となり，帰納法の仮定よりこれは正である（証明終）．

---

いま $(2)$ 式を繰り返し用いることにより
$$
b_{1000} - a_{1000} = 2\prod_{i=0}^{999} (2^i+1) 
$$
と求められる．これを $1001= 7 \times 11 \times 13$ で割った余りを考える．$2^5+1, 2^6+1$ はそれぞれ $11,13$ の倍数であるから，$b_{1000}-a_{1000}$ を $7$ で割った余りを求めればよい．$i \geq 0$ に対して $2^{i}+1$ を $7$ で割った余りは $2,3,5$ で循環するので，$7$ を法として
$$
2\prod_{i=0}^{999} (2^i+1) \equiv (2\times 3\times 5)^{333}  \times 2^2  \equiv 4
$$
である．$143\equiv 3 \pmod{7}$ に留意すれば，$b_{1000}-a_{1000}$ を $1001$ で割った余りは $6\times 143=\textbf{858}$ である．
公式解説
https://onlinemathcontest.com/contests/omcb019/editorial/11367
　$c_n=b_n-a_n$ とする. 整数 $k$ によって
　$$\left\lbrace \begin{matrix} a_n=x=k(2^{n-1}+3)-b_{n-1}\\\\ b_n=y=k(2^n+3)-a_{n-1} \end{matrix} \right.$$
が成立するので, 二式の差から $c_n=k2^{n-1}+c_{n-1}$ であり整数 $N(k)=\frac{b_{n-1}+y}{a_{n-1}+x}=\frac{k(2^n+3)+c_{n-1}}{k(2^{n-1}+3)-c_{n-1}}=1+\frac{k2^{n-1}+2c_{n-1}}{k(2^{n-1}+3)-c_{n-1}}$ である.

　$N(k)$ は $k$ を変数として持つ減少関数であり, $k$ が正であれば $N(k)$ は常に $1$ より大きい. $y$ を最大化するには $k$ を最大化しなければならず, したがって $N(k)$ を最小化しなければならない.

　$N(k)=2$ は常に $k=c_{n-1}$ の解を持つ. $c_n=(2^{n-1}+1)c_{n-1}$ であり, $b_{1000}-a_{1000}=c_{1000}=c_0\prod_0^{999}(2^n+1)$ である.

　この後は[公式解説](https:\/\/onlinemathcontest.com\/contests\/omcb019\/editorial\/11367)と同じ方式で $c_{1000} \pmod{1001}$ を求めれば良い.
ユーザー解説
https://onlinemathcontest.com/contests/omcb019/editorial/11367/595
$$
P_0 = 1,\quad P_n = \prod_{i=0}^{n-1} (2^{i}+1) \quad (n\geq 1)
$$
とします．問題では $b_n-a_n$ を $P_n$ を用いて表しましたが，実は $a_n, b_n$ 単体についても $P_n$ を用いて表すことができます．

<details>
  <summary>ネタバレ<\/summary>
はじめに，解説中の漸化式が $b_n - 2a_n = (-1)^n$ を満たすことを数学的帰納法で示します．

 - $n=0$ の場合は $b_0 - 2 a_0 = 3-2 \times 1=1$ なので確かに成立しています．
 - ある非負整数 $k$ において $b_k - 2a_k = (-1)^k$ が成立していると仮定します．このとき，$b_{k+1} - 2a_{k+1}$ の値を解説中の漸化式に基づいて計算すると，
$$
\begin{aligned}
b_{k+1} - 2a_{k+1} 
&=\bigl( (b_k-a_k)(2^{k+1}+3) - a_k \bigl) - 2\bigl( (b_k-a_k)(2^{k}+3) - b_k \bigl) \\\\
&=-b_k + 2 a_k\\\\
&= (-1)^{k+1}
\end{aligned}
$$
となり，$n=k+1$ の場合でも成立することがわかります．
----

これを公式解説中の式 $b_n- a_n = 2P_n$ と連立することにより， 
$$\begin{cases}
a_n &= 2P_n + (-1)^{n+1}\\\\
b_n &= 4P_n + (-1)^{n+1}
\end{cases}
$$
と表記することができました（便宜上 $P_0=1$ としているので， $n=0$ の場合でもこれは成立しています）．
<\/details>
オマケ（a_n, b_n の一般項（？）について）
https://onlinemathcontest.com/contests/omcb019/editorial/11367/596
　$(a_0,b_0)=(1,3)$ を初期値として，別の $2$ つの整数の組へ更新する操作を繰り返します．$n$ 回目の更新で得られる整数の組 $(a_n, b_n)$ は以下のように与えられます：

 - $\dfrac{a_{n-1}+y}{b_{n-1}+x}=\dfrac{2^n+3}{2^{n-1}+3}$ を満たし，$\dfrac{b_{n-1}+y}{a_{n-1}+x}$ が整数となるような整数の組 $(x,y)$ のうち，$y$ が最大であるもの．

　$b_{1000}-a_{1000}$ を $1001$ で割った余りを求めてください．