トップ› 東京大学› 1979年› 理系第3問

東京大学 1979年理系第3問解説

方針・初手

数列 $\{u_n\}$ の項に $4$ の倍数が現れない、すなわちすべての自然数 $n$ について $u_n \not\equiv 0 \pmod 4$ となる条件を求める問題である。このような倍数や余りに関する数列の問題では、法を $4$ とする合同式を用いて $\{u_n\}$ の余りの規則性を調べるのが基本方針となる。与えられた漸化式に合同式を適用し、$a$ を $4$ で割った余りによって場合分けして調べる。

解法1

法を $4$ とする合同式を用いて考える。与えられた漸化式は $n \ge 3$ において、次のように表される。

$$ u_n \equiv a u_{n-2} - u_{n-1} \pmod 4 $$

正の整数 $a$ を $4$ で割った余りによって、以下の $3$ つの場合に分けて考える。

(i)

$a \equiv 0, 2 \pmod 4$ （$a$ が偶数）のとき

$a = 2k$ （$k$ は正の整数）とおける。このとき、初項と第 $2$ 項は次のようになる。

$$ \begin{aligned} u_1 &= 2 \equiv 2 \pmod 4 \\ u_2 &= a^2 + 2 = 4k^2 + 2 \equiv 2 \pmod 4 \end{aligned} $$

また、$n \ge 3$ において漸化式は次のように表される。

$$ u_n \equiv 2k \cdot u_{n-2} - u_{n-1} \pmod 4 $$

すべての自然数 $n$ に対して $u_n \equiv 2 \pmod 4$ であることを、数学的帰納法で示す。 [1] $n=1, 2$ のときは、上記の通り $u_1 \equiv 2 \pmod 4$、$u_2 \equiv 2 \pmod 4$ となり成り立つ。 [2] $n=m, m+1$ （$m \ge 1$）のとき、$u_m \equiv 2 \pmod 4$ かつ $u_{m+1} \equiv 2 \pmod 4$ が成り立つと仮定する。 $n=m+2$ のとき、漸化式より

$$ \begin{aligned} u_{m+2} &\equiv 2k \cdot u_m - u_{m+1} \pmod 4 \\ &\equiv 2k \cdot 2 - 2 \pmod 4 \\ &\equiv 4k - 2 \pmod 4 \\ &\equiv -2 \equiv 2 \pmod 4 \end{aligned} $$

となり、$n=m+2$ のときも成り立つ。 [1], [2] より、すべての自然数 $n$ について $u_n \equiv 2 \pmod 4$ である。したがって、$4$ の倍数となる項は現れない。

(ii)

$a \equiv 1 \pmod 4$ のとき

初項と第 $2$ 項は次のようになる。

$$ \begin{aligned} u_1 &= 2 \equiv 2 \pmod 4 \\ u_2 &= a^2 + 2 \equiv 1^2 + 2 = 3 \pmod 4 \end{aligned} $$

$n \ge 3$ において、漸化式は $u_n \equiv u_{n-2} - u_{n-1} \pmod 4$ となる。これを用いて $u_3, u_4$ を計算すると、

$$ \begin{aligned} u_3 &\equiv u_1 - u_2 \equiv 2 - 3 = -1 \equiv 3 \pmod 4 \\ u_4 &\equiv u_2 - u_3 \equiv 3 - 3 = 0 \pmod 4 \end{aligned} $$

よって、$u_4$ が $4$ の倍数となるため、条件を満たさない。

(iii)

$a \equiv 3 \pmod 4$ のとき

初項と第 $2$ 項は次のようになる。

$$ \begin{aligned} u_1 &= 2 \equiv 2 \pmod 4 \\ u_2 &= a^2 + 2 \equiv 3^2 + 2 = 11 \equiv 3 \pmod 4 \end{aligned} $$

$n \ge 3$ において、漸化式は $u_n \equiv 3 u_{n-2} - u_{n-1} \equiv -u_{n-2} - u_{n-1} \pmod 4$ となる。これを用いて順次計算し、隣り合う $2$ 項の余りの組 $(u_{n-1}, u_n)$ の推移を調べる。

$$ \begin{aligned} (u_1, u_2) &\equiv (2, 3) \pmod 4 \\ u_3 &\equiv -u_1 - u_2 \equiv -2 - 3 = -5 \equiv 3 \pmod 4 \\ (u_2, u_3) &\equiv (3, 3) \pmod 4 \\ u_4 &\equiv -u_2 - u_3 \equiv -3 - 3 = -6 \equiv 2 \pmod 4 \\ (u_3, u_4) &\equiv (3, 2) \pmod 4 \\ u_5 &\equiv -u_3 - u_4 \equiv -3 - 2 = -5 \equiv 3 \pmod 4 \\ (u_4, u_5) &\equiv (2, 3) \pmod 4 \end{aligned} $$

$(u_4, u_5)$ の組が $(u_1, u_2)$ の組と一致したため、以降はこれと同じ推移を繰り返す。すなわち、法 $4$ における余りの組は $(2, 3) \to (3, 3) \to (3, 2) \to (2, 3) \to \cdots$ と周期 $3$ で遷移する。この遷移の中に余りが $0$ となる項は含まれないため、すべての自然数 $n$ について $u_n \not\equiv 0 \pmod 4$ である。したがって、$4$ の倍数となる項は現れない。

以上 (i)〜(iii) より、$4$ の倍数が現れないための条件は $a \equiv 0, 2, 3 \pmod 4$ である。

解説

数列の項が特定の数の倍数になるか（あるいはならないか）を判定する問題では、その数を法とする合同式を用いて、数列の余りの周期性を調べるのが定石である。本問の漸化式は三項間漸化式であり、$u_n$ の値は直前の $2$ 項 $u_{n-1}, u_{n-2}$ によって完全に決定される。したがって、法 $4$ での余りの組 $(u_{n-1}, u_n)$ を順に追跡すれば、有限回の操作で必ず過去に現れた組に戻り、周期性が確認できる。 $a$ を $4$ で割った余りで分類し、それぞれに対して素直に余りを計算していくことで、安全に完答に辿り着くことができる。