トップ› 京都大学› 1994年› 理系第2問

京都大学 1994年理系第2問解説

方針・初手

漸化式で定まる数列の各項を、ある数で割った余りを考える問題である。剰余に関する漸化式を立てて、数列の周期性を見抜くことが第一歩となる。 (1) では実際に余りを計算し、(2) ではその周期性を利用して和の性質を示す。(3) では (2) の結果をもとに、$n$ を周期で割った商と余りに分類して不等式を評価する。

解法1

(1)

数列 $\{a_n\}$ の定義は $a_0 = 1$、$a_1 = 2$、$a_{n+2} = a_{n+1} + a_n$ である。 $b_n$ は $a_n$ を $3$ で割った余りであるから、合同式（法 $3$）を用いて計算する。漸化式より、任意の $0$ 以上の整数 $n$ について次が成り立つ。

$$ b_{n+2} \equiv b_{n+1} + b_n \pmod 3 $$

これを用いて順に $b_n$ を求める。

$$ \begin{aligned} b_0 &= 1 \\ b_1 &= 2 \\ b_2 &\equiv 2 + 1 = 3 \equiv 0 \pmod 3 \implies b_2 = 0 \\ b_3 &\equiv 0 + 2 = 2 \pmod 3 \implies b_3 = 2 \\ b_4 &\equiv 2 + 0 = 2 \pmod 3 \implies b_4 = 2 \\ b_5 &\equiv 2 + 2 = 4 \equiv 1 \pmod 3 \implies b_5 = 1 \\ b_6 &\equiv 1 + 2 = 3 \equiv 0 \pmod 3 \implies b_6 = 0 \\ b_7 &\equiv 0 + 1 = 1 \pmod 3 \implies b_7 = 1 \\ b_8 &\equiv 1 + 0 = 1 \pmod 3 \implies b_8 = 1 \\ b_9 &\equiv 1 + 1 = 2 \pmod 3 \implies b_9 = 2 \end{aligned} $$

よって、求める $b_0, \dots, b_9$ は順に $1, 2, 0, 2, 2, 1, 0, 1, 1, 2$ である。

(2)

（1）の結果から、$b_8 = 1 = b_0$、$b_9 = 2 = b_1$ であることがわかる。数列 $\{b_n\}$ は直前の $2$ 項によって次の項がただ一つに決まるため、$b_8 = b_0$ かつ $b_9 = b_1$ が成り立てば、それ以降も同じ数列のパターンを繰り返す。すなわち、数列 $\{b_n\}$ は周期 $8$ を持ち、任意の $0$ 以上の整数 $k$ に対して $b_{k+8} = b_k$ が成り立つ。

ここで、$c_{n+8}$ は以下のように表せる。

$$ c_{n+8} = \sum_{k=0}^{n+8} b_k = \sum_{k=0}^{n} b_k + \sum_{k=n+1}^{n+8} b_k $$

右辺の第1項は $c_n$ である。第2項は連続する $8$ 項の和であるが、数列 $\{b_n\}$ は周期 $8$ を持つため、どこから連続する $8$ 項をとってもその和は等しい。したがって、第2項は $b_0$ から $b_7$ までの和に等しくなる。

$$ \sum_{k=n+1}^{n+8} b_k = \sum_{k=0}^{7} b_k = c_7 $$

以上より、次が成り立つ。

$$ c_{n+8} = c_n + c_7 $$

(3)

（1）より、$b_0, b_1, \dots, b_7$ は $1, 2, 0, 2, 2, 1, 0, 1$ であるから、$c_7$ の値は次のようになる。

$$ c_7 = 1 + 2 + 0 + 2 + 2 + 1 + 0 + 1 = 9 $$

任意の $0$ 以上の整数 $n$ は、整数 $q \geqq 0$ と整数 $0 \leqq r \leqq 7$ を用いて $n = 8q + r$ と表すことができる。（2）の $c_{n+8} = c_n + c_7$ を繰り返し用いると、$c_n$ は次のように計算できる。

$$ c_n = c_{8q+r} = c_r + q c_7 = c_r + 9q $$

示すべき不等式 $n+1 \leqq c_n \leqq \frac{3}{2}(n+1)$ は、次のように書き換えられる。

$$ 8q + r + 1 \leqq c_r + 9q \leqq \frac{3}{2}(8q + r + 1) $$

この不等式を、左辺の不等号と右辺の不等号に分けて証明する。

(i) 左側の不等式 $n+1 \leqq c_n$ について

$$ c_n - (n+1) = (c_r + 9q) - (8q + r + 1) = q + c_r - (r + 1) $$

(ii) 右側の不等式 $c_n \leqq \frac{3}{2}(n+1)$ について

$$ \frac{3}{2}(n+1) - c_n = \frac{3}{2}(8q + r + 1) - (c_r + 9q) = 3q + \frac{3}{2}(r + 1) - c_r $$

ここで、$r = 0, 1, 2, 3, 4, 5, 6, 7$ の各場合における $c_r$、$r+1$、$\frac{3}{2}(r+1)$ の値を表にまとめる。

$r$	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$
$b_r$	$1$	$2$	$0$	$2$	$2$	$1$	$0$	$1$
$c_r$	$1$	$3$	$3$	$5$	$7$	$8$	$8$	$9$
$r+1$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$
$\frac{3}{2}(r+1)$	$1.5$	$3$	$4.5$	$6$	$7.5$	$9$	$10.5$	$12$

表より、すべての $r$ ($0 \leqq r \leqq 7$) において $r+1 \leqq c_r \leqq \frac{3}{2}(r+1)$ が成り立つ。すなわち、$c_r - (r+1) \geqq 0$ かつ $\frac{3}{2}(r+1) - c_r \geqq 0$ である。

また、$q \geqq 0$ であるから、（i）より $c_n - (n+1) = q + c_r - (r + 1) \geqq 0$ （ii）より $\frac{3}{2}(n+1) - c_n = 3q + \frac{3}{2}(r + 1) - c_r \geqq 0$

したがって、すべての $0$ 以上の整数 $n$ について $n+1 \leqq c_n \leqq \frac{3}{2}(n+1)$ が成り立つことが示された。

解説

整数を割った余りに関する漸化式は、取り得る値の種類が有限であるため、必ずどこかで過去の連続する項の組と同じものが現れ、周期性を持つことになる。本問のように2項間の漸化式であれば、連続する2つの項の組が一致した時点で周期が確定する。 (3)は、周期性を持つ数列の和（あるいは一般項）に関する証明の典型手法である「周期で割った商 $q$ と余り $r$ で分類する」というアプローチを問うている。商 $q$ に依存する部分は等差数列的に振る舞い、余り $r$ に依存する部分は高々有限個（本問では8個）のパターンしかないため、しらみつぶしに調べることが可能となる。