東京大学 1993年 文系 第2問 解説

方針・初手

数列の各項が偶数であるか奇数であるかのみが問われているため、2を法とする合同式を用いて考えるのが最も簡潔である。与えられた漸化式を2を法として書き換え、数列 $\{a_n\}$ の偶奇の規則性を見つける。

解法1

すべての整数 $n \geqq 1$ について、2を法とする合同式で考える。

与えられた漸化式は $a_{n+2} = 3a_{n+1} - 7a_n$ である。

ここで、$3 \equiv 1 \pmod 2$、$ -7 \equiv 1 \pmod 2$ であるから、漸化式は次のように表される。

$$ a_{n+2} \equiv a_{n+1} + a_n \pmod 2 $$

また、初期条件は $a_1 = 1 \equiv 1 \pmod 2$、$a_2 = 3 \equiv 1 \pmod 2$ である。

この合同式の漸化式を用いて、$a_n$ の2を法とする剰余を順に計算すると、以下のようになる。

$a_1 \equiv 1 \pmod 2$

$a_2 \equiv 1 \pmod 2$

$a_3 \equiv a_2 + a_1 \equiv 1 + 1 \equiv 0 \pmod 2$

$a_4 \equiv a_3 + a_2 \equiv 0 + 1 \equiv 1 \pmod 2$

$a_5 \equiv a_4 + a_3 \equiv 1 + 0 \equiv 1 \pmod 2$

$a_6 \equiv a_5 + a_4 \equiv 1 + 1 \equiv 0 \pmod 2$

このように計算していくと、連続する2項組 $(a_n \pmod 2, a_{n+1} \pmod 2)$ は $(1, 1) \to (1, 0) \to (0, 1) \to (1, 1)$ となり、以降は同じ周期で繰り返される。

すなわち、数列 $a_n \pmod 2$ は $1, 1, 0$ の周期3の繰り返しとなる。

したがって、$a_n \equiv 0 \pmod 2$ となるのは、項番号 $n$ が3の倍数のときである。

これを数学的帰納法を用いて厳密に示す。

「すべての正の整数 $k$ について、$a_{3k-2} \equiv 1 \pmod 2$、$a_{3k-1} \equiv 1 \pmod 2$、$a_{3k} \equiv 0 \pmod 2$ が成り立つ」ことを示す。

(i)

$k=1$ のとき

$a_1 \equiv 1 \pmod 2$、$a_2 \equiv 1 \pmod 2$、$a_3 \equiv 0 \pmod 2$ であり、成立する。

(ii)

$k=m$ （$m$ は正の整数）のとき

$a_{3m-2} \equiv 1 \pmod 2$、$a_{3m-1} \equiv 1 \pmod 2$、$a_{3m} \equiv 0 \pmod 2$ が成り立つと仮定する。

$k=m+1$ のとき、漸化式より以下が成り立つ。

$$ a_{3(m+1)-2} = a_{3m+1} \equiv a_{3m} + a_{3m-1} \equiv 0 + 1 \equiv 1 \pmod 2 $$

$$ a_{3(m+1)-1} = a_{3m+2} \equiv a_{3m+1} + a_{3m} \equiv 1 + 0 \equiv 1 \pmod 2 $$

$$ a_{3(m+1)} = a_{3m+3} \equiv a_{3m+2} + a_{3m+1} \equiv 1 + 1 \equiv 0 \pmod 2 $$

よって、$k=m+1$ のときも成り立つ。

（i）、（ii） より、すべての正の整数 $k$ について、$a_{3k} \equiv 0 \pmod 2$ であり、それ以外の項は奇数となる。

ゆえに、$a_n$ が偶数となる $n$ は、3の倍数である。

解説

整数の性質（特に偶奇や倍数判定）と漸化式が絡む問題では、法を定めた合同式（剰余類）を考えると見通しが良くなることが多い。

本問では「偶数となる」条件を求めるため、法を2として計算を進めるのが定石である。

合同式の性質により、加法、減法、乗法については元の漸化式をそのまま合同式に置き換えることができるため、計算量が大幅に削減される。

また、漸化式で定まる数列の剰余は、取り得る値の組が有限個（本問では2つの項から次が定まるため、高々 $2^2=4$ 通り）であるため、必ず周期性を持つことも重要なポイントである。

答え

$n$ は3の倍数（または $n=3k$ ただし $k$ は正の整数）