2022年 京都大学 理系 第6問

---

1. 問題の構造

1.1 記法

本稿を通じて次の記号を用いる。$n$ は正の整数を動く。

• $c_n=2\cos\dfrac{2\pi x_n}{3}$ を余弦項と呼ぶ。漸化式は $x_{n+1}-x_n=n+c_n$ と書ける。
• 数列 $(a_n)$ の階差を $\Delta a_n=a_{n+1}-a_n$ と書く。
• $r_n\in\lbrace 0,1,2\rbrace$ を，$n-1$ を $3$ で割った余りとする。$n\equiv1,2,0\pmod 3$ はそれぞれ $r_n=0,1,2$ と同値である。
• 非負整数 $k$ に対し $\binom{k}{2}=\frac{k(k-1)}{2}$ とする。特に $\binom{n-1}{2}=\frac{(n-1)(n-2)}{2}$，$\binom{0}{2}=\binom{1}{2}=0$ である。
• 命題 $P$ の指示関数を $\mathbf{1}_{P}$（$P$ が真なら $1$，偽なら $0$）と書く。
• $\Psi_n(t)=t+n+2\cos\dfrac{2\pi t}{3}$（$t\in\mathbb{R}$）とおく。漸化式は $x_{n+1}=\Psi_n(x_n)$ である。
• 第5章では $\omega=e^{2\pi i/3}$ を用いる。

1.2 余弦項の二値性と法 3 での線形化

漸化式は $x_n$ を余弦の中に含み，見かけ上は非線形かつ自己参照的である。しかし $x_n$ が整数である限り，余弦の引数は $\frac{2\pi}{3}$ の整数倍に限られる。

論証の順序が本質的である。合同式は整数に対して定義されるから，$c_n\equiv-1$ と書く前に $c_n$ が整数であること，すなわち $x_n\in\mathbb{Z}$ を確定させなければならない。
(L) の右辺には $c_n$ が現れない。余弦項は $x_n$ の値に応じて $2$ と $-1$ を切り替えるが，その差 $3$ は法 $3$ では見えない。実際 補題1 より
$$ x_{n+1}=x_n+(n-1)+3\cdot\mathbf{1}_{3\mid x_n} $$
と書け，状態に依存する部分は $3$ の倍数の加算にすぎず，その発生を決める $x_n\bmod 3$ 自身を変えない。すなわち帰還（フィードバック）は法 $3$ の力学に影響しない。これが非線形性が見かけだけである理由である。
構造的には，$\Psi_n(t+3)=\Psi_n(t)+3$ が成り立つ。漸化式は $3$ による平行移動と可換であり，法 $3$ への還元が整合的に定義される。同時に，$(x_n)$ が漸化式を満たせば $(x_n+3)$ も同じ漸化式を満たすから，解の決定には初期値 $x_1=0$ が不可欠である（ 3.4 節 ）。

1.3 比較数列の一本化と階差

$y_n$ は3系列に分けて定義されているが，一つの式にまとまる。

$\Delta y_n$ は $2,2,-1$ を繰り返す周期 $3$ の列で，1周期の平均は $(2+2-1)/3=1$ である。$y_n=(n-1)+r_n$ は，平均 $1$ による一次の部分と周期 $3$ ののこぎり波 $r_n$ への分解にほかならない（ 5.6 節 ）。3系列による定義はこの単純な構造を覆い隠している。

1.4 局所等式への帰着

$\Delta y_n$ の値域 $\lbrace 2,-1\rbrace$ は余弦項の値域と一致する。この一致が設計の中核であり，次の命題により問題全体が一つの局所等式に帰着する。

以下のすべての解法は，(K) すなわち (iii) を示す異なる経路である。(i) と (ii) が同値であるから，(K) は答の十分条件であるだけでなく必要条件でもあり，本問の数学的内容を過不足なく表す。(K) の右辺は $n$ のみの既知関数であり，(K) は「自己参照的に見える余弦項が，実は $n$ のみで定まる」という主張である。

1.5 作問の設計と背景

以上の構造から，作問の設計は次のように読める（数値設定からの分析であり，出題者の意図についての推定を含む）。

• 逆算による構成：答 $\binom{n}{2}$ と周期列 $2,2,-1$ を用意し，その累積和を $y_n$，$x_n=\binom{n}{2}+y_n$ とすれば $\Delta x_n=n+\Delta y_n$ となる。周期列を $2\cos\frac{2\pi x_n}{3}$ と書き換えることで，既知の周期列が自己参照的な非線形項に偽装される。実際 $c_n=1-2\cos\frac{2\pi n}{3}$ であり（ 3.7 節 ），余弦項は $n$ のみの関数である。
• 偽装の整合性：書き換えが矛盾しないのは， 補題2 により $x_n\bmod 3$ が帰還と無関係に定まるからである。これを支えるのは，余弦の引数の周期が $3$ であることと，値域 $\lbrace 2,-1\rbrace$ が単一の剰余類 $-1+3\mathbb{Z}$ に含まれることの二点である。整数値をとる $2\cos\frac{2\pi k}{m}$ のうち値域が法 $m$ の単一の剰余類に入るのは $m\leqq3$ に限られ（ 命題7 ），$m=2$ では $2\cos\pi k=2(-1)^k$ にすぎない。$m=3$ は，単一の余弦でこの性質を実現する最大の法である。
• 初期値の選択：$x_1$ を任意の整数に変えても $x_n\bmod 3$ は周期 $3$ をもつが，余弦項の列は $x_1\equiv0,1,2\pmod 3$ に応じて $(2,2,-1)$，$(-1,-1,-1)$，$(-1,-1,2)$ の繰り返しとなる（ 5.2 節 ）。$x_1=0$ は $y_n$ の与え方と整合する位相を選んでおり，$x_1\equiv1$ では $c_n=-1$（定数）となって問題が自明化する。
• 問う量の選択：$x_n$ 自体は $x_n=\binom{n}{2}+2(n-1)-3\left\lfloor\frac{n-1}{3}\right\rfloor$ であり（ 3.2 節 ），ガウス記号を含む。差 $x_n-y_n$ を問うことで，答は多項式 $\binom{n}{2}$ となる。
• 表示の選択：$y_n$ を3系列で与えることで，$\Delta y_n$ の周期構造は直接には見えない。誘導はなく，整数性・法 $3$・階差という三つの観察を自力で連結することが求められる。

1.6 構造から導かれる解法の分岐

---

2. 本解：法 3 による状態追跡

2.1 方針

整数性を確定した後，漸化式を法 $3$ で読んで線形化し，$x_n\bmod 3$ を $n$ の式として求める。そこから余弦項の値を $n\bmod 3$ で決定し，$y_n$ の階差と比較して (K) を得る。最後に差 $x_n-y_n$ の階差を和分する。

2.2 解答

$c_n=2\cos\frac{2\pi x_n}{3}$ とおく。
（整数性）整数 $k$ について，余弦の周期性より $2\cos\frac{2\pi k}{3}$ は $k$ を $3$ で割った余りのみで定まり，
$$ 2\cos\frac{2\pi k}{3}=\begin{cases}2&(k\equiv0\pmod 3),\\-1&(k\equiv1,2\pmod 3)\end{cases} \tag{1} $$
である。$x_1=0$ は整数であり，$x_n$ が整数なら (1) より $c_n\in\lbrace 2,-1\rbrace$ となって $x_{n+1}=x_n+n+c_n$ も整数である。よって数学的帰納法により，すべての $n$ で $x_n\in\mathbb{Z}$，$c_n\in\lbrace 2,-1\rbrace$ である。
（法 3 での線形化）$2\equiv-1\pmod 3$ より $c_n\equiv-1\pmod 3$ であるから，$k\geqq1$ に対し $x_{k+1}-x_k\equiv k-1\pmod 3$ である。これを $k=1,\ldots,n-1$ について加え，$x_1=0$ を用いると
$$ x_n\equiv\sum_{k=1}^{n-1}(k-1)=\frac{(n-1)(n-2)}{2}\pmod 3\qquad(n\geqq1) \tag{2} $$
を得る（$n=1$ では両辺とも $0$）。
（剰余の決定）$t_n=\frac{(n-1)(n-2)}{2}$ は整数であり，
$$ t_{n+3}-t_n=\frac{(n+2)(n+1)-(n-1)(n-2)}{2}=3n\equiv0\pmod 3. $$
$t_1=0$，$t_2=0$，$t_3=1$ であるから，帰納的に $t_n\bmod 3$ は $0,0,1$ を繰り返す。(2) と合わせて
$$ x_n\equiv\begin{cases}0&(n\equiv1,2\pmod 3),\\1&(n\equiv0\pmod 3).\end{cases} \tag{3} $$
(1)，(3) より
$$ c_n=\begin{cases}2&(n\equiv1,2\pmod 3),\\-1&(n\equiv0\pmod 3).\end{cases} \tag{4} $$
（$y_n$ の階差）$m\geqq0$ に対し
$$ y_{3m+2}-y_{3m+1}=2,\qquad y_{3m+3}-y_{3m+2}=2,\qquad y_{3m+4}-y_{3m+3}=3(m+1)-(3m+4)=-1. $$
$n\geqq1$ は $3m+1,\ 3m+2,\ 3m+3$（$m\geqq0$）のいずれか一つの形に一意に表されるから
$$ y_{n+1}-y_n=\begin{cases}2&(n\equiv1,2\pmod 3),\\-1&(n\equiv0\pmod 3).\end{cases} \tag{5} $$
（結論）(4)，(5) より，すべての $n$ で $c_n=y_{n+1}-y_n$ である。ゆえに
$$ (x_{n+1}-y_{n+1})-(x_n-y_n)=n+c_n-(y_{n+1}-y_n)=n. $$
$x_1-y_1=0-0=0$ であるから，$n\geqq1$ に対し
$$ x_n-y_n=\sum_{k=1}^{n-1}k=\frac{n(n-1)}{2}. $$
$$ \boxed{\ x_n-y_n=\frac{n(n-1)}{2}\ } $$

2.3 検証・検算

• 数値：$x_n-y_n$ は $\binom{n}{2}$ に一致し，(3)，(4)，(5) の周期パターンも確認できる。ただし数値の一致は証明ではなく，周期性は (2) と $t_{n+3}\equiv t_n$ によって保証されている。
• 1周期の和：連続する3項について $c_n+c_{n+1}+c_{n+2}=3=y_{n+3}-y_n$ であり，$x_{n+3}-x_n=3n+6\equiv0\pmod 3$ は (3) と整合する。
• 漸近挙動：$\Delta x_n=n+O(1)$ より $x_n=\frac{n^2}{2}+O(n)$，また $y_n=O(n)$ であるから，$x_n-y_n$ の主要項は $\frac{n^2}{2}$ であり答と整合する。
• 論証上の要所：合同式の適用は整数性の確定後に行っている。また (2) の右辺の剰余を，$2$ による除算を含む式の直接計算ではなく，$t_{n+3}-t_n=3n$ による周期性に帰着させている。

---

3. 別解と参考解

3.1〜3.2 節は本解の一部に対する別証・他の導出，3.3〜3.4 節は高校数学の範囲で完結する独立な別解，3.5〜3.6 節は保存量と計数の観点を示す参考解である。

3.1 $x_n\bmod 3$ の別導出：剰余の組の遷移

着想・方針

(L) によれば，$x_{n+1}\bmod 3$ は組 $(n\bmod 3,\ x_n\bmod 3)$ のみで定まる。したがってこの組は有限集合 $(\mathbb{Z}/3\mathbb{Z})^2$ 上の一定の写像で遷移し，和分の計算なしに周期が得られる。

解答

$\mathbb{Z}/3\mathbb{Z}$ の元を代表 $0,1,2$ で表し，$P_n=(n\bmod 3,\ x_n\bmod 3)$，$\Phi(s,\rho)=(s+1,\ \rho+s-1)$（成分は法 $3$）とおく。 補題2 の (L) より $P_{n+1}=\Phi(P_n)$ である。$P_1=(1,0)$ から
$$ P_1=(1,0)\ \longmapsto\ P_2=(2,0)\ \longmapsto\ P_3=(0,1)\ \longmapsto\ P_4=(1,0)=P_1. $$
$P_n=\Phi^{n-1}(P_1)$ であり，$\Phi^3(P_1)=P_1$ より $P_{n+3}=\Phi^{n-1}\bigl(\Phi^3(P_1)\bigr)=P_n$ である。よって $x_n\bmod 3$ は $0,0,1$ を繰り返し，本解の (3) を得る。以下は本解と同じである。

検証・検算

一般に $\Phi^3(s,\rho)=\bigl(s,\ \rho+(s-1)+s+(s+1)\bigr)=(s,\ \rho+3s)=(s,\rho)$ であり，$\Phi^3$ は9状態すべてを固定する（ 5.2 節 ）。初期状態 $(1,0)$ から訪れる状態は9個のうち3個のみである。

3.2 $x_n-y_n$ の他の導出：$x_n$ の閉形式

着想・方針

本解の (4) が得られれば，余弦項は $n$ の既知関数である。漸化式を直接和分して $x_n$ の閉形式を求め， 補題3 の $y_n$ の閉形式と比較する。

解答

4. は $c_n=2-3\cdot\mathbf{1}_{3\mid n}$ と書ける。$1\leqq k\leqq n-1$ の範囲にある $3$ の倍数の個数は $\left\lfloor\frac{n-1}{3}\right\rfloor$ であるから
   $$ x_n=\sum_{k=1}^{n-1}\left(k+2-3\cdot\mathbf{1}_{3\mid k}\right)=\binom{n}{2}+2(n-1)-3\left\lfloor\frac{n-1}{3}\right\rfloor. $$
   補題3 より $y_n=2(n-1)-3\left\lfloor\frac{n-1}{3}\right\rfloor$ であるから，$x_n-y_n=\binom{n}{2}$ である。

検証・検算

$n=7$ で $21+12-6=27=x_7$ である。ガウス記号を含む部分が $x_n$ と $y_n$ で完全に一致し，差をとると消える。これは問う量として $x_n-y_n$ が選ばれた理由を示している（ 1.5 節 ）。本節は (4) を前提とするから，独立な解法ではなく本解の後処理である。

3.3 別解1：余弦補正項の周期性

着想・方針

(K) の証明に必要なのは $x_n\bmod 3$ の一般形ではなく，余弦項 $c_n$ の値の列だけである。$c_n$ を未知の数列とみなし，その周期性 $c_{n+3}=c_n$ のみを直接示す。

解答

補題2 より $x_n\in\mathbb{Z}$ であり，$x_{k+1}-x_k\equiv k-1\pmod 3$ である。これを $k=n,\ n+1,\ n+2$ について加えると
$$ x_{n+3}-x_n\equiv(n-1)+n+(n+1)=3n\equiv0\pmod 3. $$
$c_n$ は $x_n$ を $3$ で割った余りのみで定まるから（ 補題1 ），$c_{n+3}=c_n$ である。また $x_1=0$，$x_2=0+1+2=3$，$x_3=3+2+2=7$ より $c_1=2$，$c_2=2$，$c_3=-1$ である。
一方 補題3 より $\Delta y_n$ も周期 $3$ をもち，$\Delta y_1=2$，$\Delta y_2=2$，$\Delta y_3=-1$ である。周期 $3$ の二つの数列が $n=1,2,3$ で一致すれば，$n$ に関する帰納法によりすべての $n$ で一致する。よって $c_n=\Delta y_n$，すなわち (K) が成り立ち， 命題4 により $x_n-y_n=\binom{n}{2}$ である。

検証・検算

$x_4=7+3-1=9\equiv x_1\pmod 3$ と，周期が実際に閉じていることを確認できる。「最初の3項が $2,2,-1$ であるから周期 $3$」とする推論は誤りであり，周期性の根拠は $x_{n+3}\equiv x_n$ の証明にある。また $c_n+c_{n+1}+c_{n+2}=3=y_{n+3}-y_n$ と，1周期の和も一致する。

3.4 別解2：候補解の構成と一意性

着想・方針

問われているのは差 $x_n-y_n$ であり，漸化式の階差には $n$ が現れる。$n$ の離散原始関数は $\binom{n}{2}$ であるから，$x_n=y_n+\binom{n}{2}$ を予想し，右辺で定義した数列が $x_n$ と同じ初期値と漸化式を満たすことを確かめる。$x_n$ を一度も解析しない逆算型の解法である。

解答

$a_n=y_n+\binom{n}{2}$ とおく。 補題3 の $y_n=(n-1)+r_n$ と $n-1\equiv r_n\pmod 3$ より
$$ y_n\equiv2r_n\equiv-r_n\pmod 3. $$
また $2\binom{n}{2}=n(n-1)\equiv(r_n+1)r_n\pmod 3$ であり，$2$ は法 $3$ で可逆（$2\cdot2\equiv1$）であるから $\binom{n}{2}\equiv\frac{r_n(r_n+1)}{2}\pmod 3$（右辺は整数）である。よって
$$ a_n\equiv-r_n+\frac{r_n(r_n+1)}{2}=\frac{r_n(r_n-1)}{2}\pmod 3. $$
右辺は $r_n=0,1,2$ に対して $0,0,1$ であるから，$3\mid a_n\iff r_n\in\lbrace 0,1\rbrace\iff3\nmid n$ である。 補題1 より $2\cos\frac{2\pi a_n}{3}$ は $3\nmid n$ のとき $2$，$3\mid n$ のとき $-1$ であり， 補題3 よりこれは $y_{n+1}-y_n$ に等しい。したがって
$$ a_{n+1}=y_{n+1}+\binom{n+1}{2}=y_n+\binom{n}{2}+n+(y_{n+1}-y_n)=a_n+n+2\cos\frac{2\pi a_n}{3}. $$
また $a_1=y_1+\binom{1}{2}=0=x_1$ である。$(x_n)$ と $(a_n)$ はともに $u_1=0$，$u_{n+1}=\Psi_n(u_n)$ を満たすから，帰納法によりすべての $n$ で $a_n=x_n$ である。ゆえに $x_n-y_n=\binom{n}{2}$ である。

検証・検算

$a_1,\ldots,a_4=0,3,7,9$ は $x_1,\ldots,x_4$ と一致する。剰余の計算は次の表でも確認できる。

初期値の確認は省けない。 1.2 節 で見たとおり $(a_n+3)$ も同じ漸化式を満たすから，漸化式の一致だけでは $a_n=x_n$ は従わない。なお，$x_n-y_n=\binom{n}{2}$ を帰納法の仮定として次の項を示す通常の帰納法は，本解法と論理的に同型である（ 3.7 節 ）。

3.5 参考解1：移動座標による法 3 の不変量

着想・方針

(L) のドリフト $n-1$ は $\binom{n}{2}-\binom{n-1}{2}=n-1$ と階差の形に書ける。この離散原始関数を $x_n$ から引いた移動座標は，法 $3$ で動かない。漸化式を解くのではなく，保存量を設計する解法である。

解答

補題2 より $x_n\in\mathbb{Z}$，$c_n\in\lbrace 2,-1\rbrace$ である。$I_n=x_n-\binom{n-1}{2}$ とおくと $I_n\in\mathbb{Z}$ であり，
$$ I_{n+1}-I_n=(x_{n+1}-x_n)-\left\lbrace\binom{n}{2}-\binom{n-1}{2}\right\rbrace=n+c_n-(n-1)=1+c_n\in\lbrace 3,0\rbrace. $$
よって $I_{n+1}\equiv I_n\pmod 3$ であり，$I_1=0$ から $I_n\equiv0$，すなわち $x_n\equiv\binom{n-1}{2}\pmod 3$ である。これは本解の (2) であり，以下 (3)〜(5) により (K) を得て， 命題4 から $x_n-y_n=\binom{n}{2}$ である。

検証・検算

$I_1,\ldots,I_5=0,3,6,6,9$ はすべて $3$ の倍数である。引く量は $\binom{n-1}{2}$ であって答の $\binom{n}{2}$ ではない。前者は法 $3$ のドリフト $n-1$ を消すための補正，後者は差 $x_n-y_n$ の値であり，添字が一つずれている。さらに $I_n$ は法 $3$ で不変であるだけでなく，$I_n/3$ はそれまでに $1+c_k=3$ となった回数に等しい（参考解2）。

3.6 参考解2：指示関数化と訪問回数

着想・方針

補題1 より $c_n=-1+3\cdot\mathbf{1}_{3\mid x_n}$ であるから，漸化式は
$$ x_{n+1}=x_n+(n-1)+3\cdot\mathbf{1}_{3\mid x_n} $$
となる。第 $n$ 段階では $n-1$ だけ進み，$3$ の倍数にいるときに限り追加で $3$ 進む。三角関数を計数に置き換え，$x_n$ と $y_n$ が同じ訪問回数を共有することを示して大域的に消去する。

解答

$N_n=\#\lbrace k\mid 1\leqq k\leqq n-1,\ 3\mid x_k\rbrace$ とおく。上式を $k=1,\ldots,n-1$ について加えると，等式として
$$ x_n=\binom{n-1}{2}+3N_n \tag{6} $$
を得る。特に $x_k\equiv\binom{k-1}{2}\pmod 3$ であり，追加の $3$ は剰余を変えないから，その発生時刻は追加を無視した基準軌道 $\binom{k-1}{2}$ だけで決まる。本解と同様に，$t_{k+3}\equiv t_k$ と $t_1,t_2,t_3=0,0,1$ より $3\mid\binom{k-1}{2}\iff3\nmid k$ であるから
$$ N_n=\#\lbrace k\mid 1\leqq k\leqq n-1,\ 3\nmid k\rbrace=(n-1)-\left\lfloor\frac{n-1}{3}\right\rfloor. $$
一方 補題3 より
$$ y_n=2(n-1)-3\left\lfloor\frac{n-1}{3}\right\rfloor=3N_n-(n-1). $$
これを (6) から引いて
$$ x_n-y_n=\binom{n-1}{2}+(n-1)=\binom{n}{2}. $$

検証・検算

$n=4$ では，$x_1,x_2,x_3=0,3,7$ のうち $3$ の倍数は2個で $N_4=2=3-1$ であり，$x_4=3+6=9$，$y_4=6-3=3$ となる。(6) の $3N_n$ は参考解1 の $I_n$ そのものである。本解法は $x_n\bmod 3$ の決定を参考解1 と共有するが，(K) という局所的な一致ではなく，共通の計数 $3N_n$ の大域的な相殺によって答に達する点で，消去の機構が異なる。

3.7 同じ系列に属する変形

以下は独立の解法とは数えず，既出の解法の表現違いまたは後処理として扱う。

• 直接の数学的帰納法：数項から $x_n-y_n=\binom{n}{2}$ を予想し，これを帰納法の仮定として $x_n\bmod 3$ を求め，次の項を示す方法。別解2 と論理的に同型である。
• 漸化式の和分：$x_n=\binom{n}{2}+\sum_{k=1}^{n-1}c_k$ と $y_n=\sum_{k=1}^{n-1}\Delta y_k$（$y_1=0$）を比べる見方。 命題4 の累積形であり，$c_k=\Delta y_k$ の証明には本解または別解1 を要する。
• 座標変換 $X_n=x_n-\binom{n}{2}$：$X_{n+1}=X_n+2\cos\left\lbrace\frac{2\pi}{3}\left(X_n+\binom{n}{2}\right)\right\rbrace$ となり，$X_n=y_n$ を示す問題に変わる。別解2 と同値であり，$X_n$ の数項が $y_n$ と一致することから $X_n=y_n$ と結論してはならない。
• 3項ブロック：$c_n$ の周期性から $x_{3m+1}=\frac{9m(m+1)}{2}$，$x_{3m+2}=x_{3m+1}+3m+3$，$x_{3m+3}=x_{3m+1}+6m+7$ を得て $y_n$ を引く方法。別解1 の展開である。
• 自己参照の除去：(4) は $c_n=1-2\cos\frac{2\pi n}{3}$ と書ける。漸化式は $x_{n+1}=x_n+n+1-2\cos\frac{2\pi n}{3}$ という，$x_n$ に依存しない線形の形になり，$\Delta y_n$ も同じ式で表される。
• 1の3乗根：$u_n=\omega^{x_n}$ とおくと，$c_n\equiv-1\pmod 3$ より $\omega^{c_n}=\omega^{-1}$ であるから $u_{n+1}=\omega^{n-1}u_n$，$u_n=\omega^{\binom{n-1}{2}}$ となる。また $Z_n=\omega^{I_n}$ は $Z_{n+1}=Z_n$ を満たす。本解・参考解1 の乗法的表示であり，$\omega^{x_n}$ が単位円上の正三角形の頂点を巡ることは剰余の幾何的な言い換えである。
• 床関数・離散フーリエ展開・生成関数：周期性の確定後に周期列の和を閉形式で表す後処理である（ 3.2 節 ， 5.6 節 ）。
  次のものは，独立の解法として採用しない。
• 余弦を連続関数として解析する方法（増減・凸性・微分）：決定的な情報である $x_n\in\mathbb{Z}$ を用いず，情報を増やさない。
• 漸化式全体に母関数を適用する方法：非線形項のため直接には適用できない。
• 数項の計算から周期または一般項を断定する方法：証明にならない。

3.8 解法の比較

すべての解法は高校数学の範囲で完結する。試験場での第一選択は本解である。各段階（整数性，合同，剰余，階差の一致，和分）が問題文から最短距離にあり，(3)，(4)，(5) の各段で数値による検算ができる。$y_n$ の階差に先に気付いた場合は別解1 が最短であり，数項から三角数が見えた場合は別解2 が最も記述量が少ない。参考解は，(L) の背後にある「帰還が剰余を変えない」という構造を，保存量と計数という二つの側面から明示する。

---

4. 汎用的な探索手順

本問から抽出される，状態に依存する関数を含む漸化式に対する探索手順を述べる。

4.1 意思決定の流れ

1. 非線形関数の入力がとりうる値の集合を調べる。初期値と漸化式から整数性などの離散性が帰納的に従えば，関数は有限個の値しかとらない。
2. 関数値が入力のどの情報に依存するかを特定し，状態をその粒度まで粗くする。本問では $x_n\bmod 3$ である。漸化式がその粗視化と整合すること（本問では $\Psi_n(t+3)=\Psi_n(t)+3$）を確かめる。
3. 関数の値域が単一の剰余類に入る法を探す。見つかれば，その法での力学は帰還から切り離され，$n$ のみで決まる（ 定理5 ）。
4. 場合分けで定義された比較数列は，値ではなく階差を見る。周期的な階差は，平均による一次の部分と周期部分に分解される。
5. 求める量が差であれば差の階差をとり，示すべき局所等式を特定する。その等式が答と同値であるかも確かめる（ 命題4 ）。
6. 局所等式の証明経路を選ぶ。状態を解く（本解），観測量の周期だけを解く（別解1），候補解を検証する（別解2），保存量を作る（参考解1），計数に置き換える（参考解2）。
7. 周期性は数項の一致からではなく，$x_{n+3}\equiv x_n$ や $\Phi^3(P_1)=P_1$ などの構造的事実から導く。
8. 検算する。初期の数項，1周期の和，漸近挙動，初期値を変えたときの挙動を確かめる。

4.2 症状と有効な表現

4.3 抽象化：剰余を保つ帰還

本問の核心は次の形に一般化される。

本問は $m=3$，$\gamma=-1$，$a_k=k$，$x_1=0$，$F(k)=2\cos\frac{2\pi k}{3}$ の場合である。(i) は $x_n\equiv\binom{n-1}{2}\pmod 3$ を与え，(ii) の $Y_n$ は問題の $y_n$ に一致する（ 補題3 と本解の (4)）。問題文は $Y_n$ を3系列の形で与え，$x_n-Y_n=\binom{n}{2}$ を問うている。
条件 $F(k)\equiv\gamma\pmod m$ を満たす $F$ は，一般の $m$ に対して 命題6 により $F_m(k)=\sum_{j=1}^{m-1}\cos\frac{2\pi jk}{m}=m\cdot\mathbf{1}_{m\mid k}-1$ として三角関数で構成できる。$m=3$ では $F_3(k)=2\cos\frac{2\pi k}{3}$ である。

4.4 類題設計への応用

定理5 は類題の設計原理としても読める。法 $m$ と $F_m$ を選び，駆動項 $a_n$ と初期値 $x_1$ を与えると，$x_n\bmod m$ は $x_1+\sum_{k=1}^{n-1}(a_k-1)$ で定まり，$F_m(x_n)$ は $n$ の既知関数となる。その累積和 $Y_n$ を場合分けや床関数で偽装して与え，$x_n-Y_n$ を問えばよい。初期値は余弦項が定数にならない位相を選ぶ必要がある（本問で $x_1\equiv1$ とすると $c_n=-1$ となる。 1.5 節 ）。

---

5. 発展事項

5.1 高校数学と一般理論の境界

本解・別解・参考解はすべて左欄の範囲で完結する。右欄は，それらの計算が成り立つ理由を説明する理論である。

5.2 同変性と商力学系

$\Psi_n(t+3)=\Psi_n(t)+3$ であるから，$\Psi_n$ は $\mathbb{R}/3\mathbb{Z}$ 上の写像を誘導する。整数点に制限すると， 補題2 により $\mathbb{Z}/3\mathbb{Z}$ 上の写像 $\rho\mapsto\rho+n-1$ となる。これは状態に依存しない平行移動であり，時間 $n$ に依存する回転である。時間 $n\bmod 3$ も状態に含めると，自律的な写像
$$ \Phi:(\mathbb{Z}/3\mathbb{Z})^2\to(\mathbb{Z}/3\mathbb{Z})^2,\qquad\Phi(s,\rho)=(s+1,\ \rho+s-1) $$
が得られる。これは底空間 $\mathbb{Z}/3\mathbb{Z}$ 上の回転 $s\mapsto s+1$ の上に，ファイバー方向の平行移動 $\rho\mapsto\rho+(s-1)$ を重ねた歪積である。ファイバー方向の移動量の1周期の和は $(1-1)+(2-1)+(0-1)=0$ であるから $\Phi^3=\mathrm{id}$ となり，9状態は長さ $3$ の三つの軌道に分かれる。初期値 $x_1$ の剰余が軌道を選ぶ。

周期 $3$ は初期値によらないが，周期列の形は初期値に依存する。問題の $y_n$ は第1行の軌道に合わせて与えられている。

5.3 指標の直交関係

$m=3$ では $\cos\frac{4\pi k}{3}=\cos\frac{2\pi k}{3}$ であるから左辺は $2\cos\frac{2\pi k}{3}$ となり， 補題1 の $1+2\cos\frac{2\pi k}{3}=3\cdot\mathbf{1}_{3\mid k}$ が再現される。すなわち本問の余弦項は，$\mathbb{Z}/3\mathbb{Z}$ の非自明な指標 $k\mapsto\omega^{k}$，$k\mapsto\omega^{-k}$ の和であり，$3\cdot\mathbf{1}_{3\mid k}$ の離散フーリエ展開 $\sum_{j=0}^{2}\omega^{jk}$ から定数項を除いたものである。参考解2 の指示関数化は，この展開を逆にたどる操作にあたる。

5.4 Eisenstein 整数における合同

$2\equiv-1\pmod 3$ という一見偶然の一致には，代数的整数論による説明がある。$\mathbb{Z}[\omega]=\lbrace a+b\omega\mid a,b\in\mathbb{Z}\rbrace$（Eisenstein 整数）において $\lambda=1-\omega$ とおくと，$\omega^2=-1-\omega$ より
$$ \lambda^2=1-2\omega+\omega^2=-3\omega,\qquad\text{すなわち}\qquad3=-\omega^2\lambda^2. $$
$\omega\equiv1\pmod\lambda$ であるから，任意の整数 $k$ に対して $\omega^k+\omega^{-k}\equiv2\pmod\lambda$ である（$\omega^{-1}=\omega^2\in\mathbb{Z}[\omega]$）。一方，有理整数 $z$ について $\lambda\mid z\iff3\mid z$ が成り立つ。実際，ノルム $N(a+b\omega)=a^2-ab+b^2$ は乗法的で $N(\lambda)=3$ であり，$z=\lambda\beta$ ならば $z^2=3N(\beta)$ より $3\mid z$ である。逆は $\lambda\mid3$ による。$2\cos\frac{2\pi k}{3}=\omega^k+\omega^{-k}$ は有理整数であるから
$$ 2\cos\frac{2\pi k}{3}\equiv2\pmod 3. $$
すなわち，$2$ と $-1$ が法 $3$ で等しいことは，$1$ の3乗根がすべて素元 $\lambda$ を法として $1$ に合同であること（$3$ が $\mathbb{Q}(\omega)$ で完全分岐すること）の帰結である。素数 $p$ と $\zeta_p=e^{2\pi i/p}$ についても同様に $\zeta_p\equiv1\pmod{1-\zeta_p}$ であり，$\sum_{j=1}^{p-1}\zeta_p^{jk}\equiv p-1\equiv-1\pmod p$ を得る。これは $m$ が素数の場合の 命題6 の合同部分の別証になる。

5.5 整数値をとる余弦と Niven の定理

したがって，単一の余弦 $2\cos\frac{2\pi x}{m}$ によって「値は変わるが法 $m$ では定数」という帰還を作れるのは $m=2,3$ に限られ，$m=2$ では $2(-1)^x$ にすぎない。$m\geqq4$ では 命題6 の和 $F_m$ が必要になる。本問の $m=3$ は，この意味で単一の余弦による構成の最大の場合である。
より強く，Niven の定理は「$\theta/\pi\in\mathbb{Q}$ かつ $\cos\theta\in\mathbb{Q}$ ならば $\cos\theta\in\lbrace 0,\pm\frac12,\pm1\rbrace$」を主張する。証明は，$D_0(X)=2$，$D_1(X)=X$，$D_{j+1}(X)=XD_j(X)-D_{j-1}(X)$ で定まる整数係数のモニック多項式（Dickson 多項式）が $D_j(2\cos\theta)=2\cos j\theta$ を満たすことによる。$\theta=\frac{2\pi p}{q}$ ならば $2\cos\theta$ はモニック整数係数多項式 $D_q(X)-2$ の根であり，有理根定理によって有理数なら整数である。同じ事実は，格子を保つ回転の位数が $1,2,3,4,6$ に限られるという結晶学的制限の背景でもある（回転行列のトレース $2\cos\frac{2\pi}{m}$ が整数でなければならない）。

5.6 差分法と周期列の離散原始関数

差分作用素 $\Delta$ と和 $\sum_{k=1}^{n-1}$ の間には，微積分学の基本定理の離散版
$$ \sum_{k=1}^{n-1}\Delta a_k=a_n-a_1 $$
が成り立つ。$\Delta\binom{n}{2}=n$ であり，一般に $\Delta\binom{n}{j}=\binom{n}{j-1}$ である。$\binom{n}{j}$ は下降階乗 $n(n-1)\cdots(n-j+1)$ を $j!$ で割ったもので，$\frac{x^j}{j!}$ の離散版にあたる。本問は $\Delta x_n=n+c_n$，$\Delta y_n=c_n$ から $\Delta(x_n-y_n)=n$ を得る構造である。
周期 $p$ の数列 $(c_k)$ の1周期の和を $S$ とすると，$g(n)=\sum_{k=1}^{n-1}\left(c_k-\frac{S}{p}\right)$ は $g(n+p)-g(n)=S-S=0$ を満たすから
$$ \sum_{k=1}^{n-1}c_k=\frac{S}{p}(n-1)+g(n)\qquad(g\text{ は周期 }p) $$
と分解される。周期関数の原始関数が「平均による一次関数と周期関数の和」になることの離散版である。本問では $p=3$，$S=3$ であり，$y_n=(n-1)+r_n$（ 補題3 ）がこの分解にあたる。
振動成分を三角関数で表すと，$c_n=1-2\cos\frac{2\pi n}{3}$ であり，のこぎり波 $r_n$ は
$$ r_n=1-\cos\frac{2\pi(n-1)}{3}-\frac{1}{\sqrt3}\sin\frac{2\pi(n-1)}{3} $$
と書ける（右辺は周期 $3$ をもち，$n=1,2,3$ で $0,1,2$ を与える）。したがって
$$ y_n=n-\cos\frac{2\pi(n-1)}{3}-\frac{1}{\sqrt3}\sin\frac{2\pi(n-1)}{3},\qquad x_n=\binom{n}{2}+y_n. $$
これは $y_n$ の3系列による定義と 3.2 節 の床関数表示を，離散フーリエ展開の形で統一したものである。

5.7 歴史的背景

合同式の記号 $\equiv$ は Gauss の『Disquisitiones Arithmeticae』（1801）に始まる。$\mathbb{Z}[\omega]$ は Eisenstein の名を冠し，19世紀に3次の相互法則の研究で用いられた。差分と和分の計算法は Newton 以来の補間法の伝統にあり，Boole の『A Treatise on the Calculus of Finite Differences』（1860）で体系的に整理された。有理数倍の角の余弦が有理数となる場合の決定は Niven の『Irrational Numbers』（1956）に収められている。指標の直交関係は，有限アーベル群上のフーリエ解析の基礎である。本問は，これらの理論が交わる最も小さな具体例の一つになっている。

---

6. 最終整理

6.1 全体の構造マップ

• 初期値 $x_1=0$ と漸化式
  • 整数性 $x_n\in\mathbb{Z}$（ 補題2 ）から，余弦項 $c_n\in\lbrace 2,-1\rbrace\subset-1+3\mathbb{Z}$（ 補題1 ）
    • 法 $3$ での線形化 (L)：$x_{n+1}\equiv x_n+n-1$（帰還は剰余を変えない）
      • 和分して $x_n\equiv\binom{n-1}{2}$ → 本解
      • 剰余の組の遷移 $\Phi$，$\Phi^3=\mathrm{id}$ → 3.1 節
      • $c_{n+3}=c_n$ のみを示す → 別解1
      • 不変量 $x_n-\binom{n-1}{2}\equiv0$ → 参考解1
      • 等式 $x_n=\binom{n-1}{2}+3N_n$ と訪問回数 → 参考解2
• 比較数列 $y_n$
  • 一本化 $y_n=(n-1)+r_n$，階差 $2,2,-1$ の繰り返し（ 補題3 ）
• 合流点：局所等式 (K) $2\cos\frac{2\pi x_n}{3}=y_{n+1}-y_n$，すなわち $3\mid x_n\iff3\nmid n$（ 命題4 ）
  • 逆方向：候補 $y_n+\binom{n}{2}$ と解の一意性 → 別解2
  • 和分：$\Delta(x_n-y_n)=n$ より $x_n-y_n=\dfrac{n(n-1)}{2}$
• 一般化：剰余を保つ帰還（ 定理5 ），指標和 $F_m$（ 命題6 ），単一の余弦による構成の限界（ 命題7 ）

6.2 数学的教訓

• 非線形関数を含む漸化式では，まず入力の集合を調べる。離散性が帰納的に従えば，関数は有限個の値しかとらない。
• 合同式は整数に対して用いる。整数性の確定が線形化に先立つ。
• 関数の値域が単一の剰余類に入る法では，状態に依存する帰還は剰余の力学に影響しない。見かけの自己参照は，法をとると消える。
• 場合分けで与えられた数列は階差で見る。周期的な階差は，平均による一次の部分と周期部分に分解される。
• 求める量が差であれば差の階差をとり，示すべき局所等式を特定する。その等式が答と同値であるかも確かめる。
• 同じ局所等式に，状態・観測量・候補解・保存量・計数という異なる入口から到達できる。
• 周期性は数項の一致ではなく，$x_{n+3}\equiv x_n$ や $\Phi^3=\mathrm{id}$ といった構造から導く。候補解の検証では初期値の一致を省かない。
• 問題文が与える補助数列 $y_n$ は，作問者が隠した構造，すなわち周期列の離散原始関数を指し示している。
  $$ \boxed{\ x_n-y_n=\frac{n(n-1)}{2}\ } $$