トップ› 京都大学› 1996年› 理系第4問

京都大学 1996年理系第4問解説

方針・初手

ガウス記号 $[x]$ を含む漸化式で定義された数列の問題です。ガウス記号の基本性質 $[x] \leqq x < [x] + 1$ （$[x]$ は整数）を常に意識して不等式評価を行います。 (1) は定義に従って順次計算するだけで求まります。 (2) は漸化式から一般項を求めるのが難しいため、数学的帰納法を用いて示します。第一の不等式 $a_n \leqq \frac{k-1}{2}$ を先に帰納法で証明し、その結果を利用して第二の不等式 $a_n \leqq a_{n+1}$ を直接示すのがスムーズです。 (3) は「一度隣り合う項が等しくなれば、それ以降はずっと定数になる」という性質を帰納法で示し、その後、ガウス記号の定義式から $a_n$ の値を絞り込みます。

解法1

(1)

$a_1 = 0, \ a_n = \left[ \frac{a_{n-1} + k}{3} \right] \ (n \geqq 2)$ である。

$k=8$ のとき

$$\begin{aligned} a_1 &= 0 \\ a_2 &= \left[ \frac{0 + 8}{3} \right] = \left[ 2.66\dots \right] = 2 \\ a_3 &= \left[ \frac{2 + 8}{3} \right] = \left[ 3.33\dots \right] = 3 \\ a_4 &= \left[ \frac{3 + 8}{3} \right] = \left[ 3.66\dots \right] = 3 \end{aligned}$$

$a_3 = a_4$ となったので、これ以降 $n \geqq 3$ に対して $a_n = 3$ である。よって、$k=8$ のときの数列は

$$ a_1 = 0, \ a_2 = 2, \ n \geqq 3 \text{ のとき } a_n = 3 $$

$k=9$ のとき

$$\begin{aligned} a_1 &= 0 \\ a_2 &= \left[ \frac{0 + 9}{3} \right] = [3] = 3 \\ a_3 &= \left[ \frac{3 + 9}{3} \right] = [4] = 4 \\ a_4 &= \left[ \frac{4 + 9}{3} \right] = \left[ 4.33\dots \right] = 4 \end{aligned}$$

$a_3 = a_4$ となったので、これ以降 $n \geqq 3$ に対して $a_n = 4$ である。よって、$k=9$ のときの数列は

$$ a_1 = 0, \ a_2 = 3, \ n \geqq 3 \text{ のとき } a_n = 4 $$

(2)

まず、すべての自然数 $n$ に対し $a_n \leqq \frac{k-1}{2}$ であることを数学的帰納法で示す。

(i)

$n=1$ のとき

$a_1 = 0$ であり、$k$ は自然数（$k \geqq 1$）であるから $\frac{k-1}{2} \geqq 0$ となり、$a_1 \leqq \frac{k-1}{2}$ は成り立つ。

(ii)

$n=m$ のとき成立すると仮定する。すなわち、$a_m \leqq \frac{k-1}{2}$ とする。

$a_m$ は整数であるから、$2a_m \leqq k-1$ が成り立つ。 $n=m+1$ のとき、ガウス記号の性質 $[x] \leqq x$ より

$$ a_{m+1} = \left[ \frac{a_m + k}{3} \right] \leqq \frac{a_m + k}{3} $$

帰納法の仮定より $a_m \leqq \frac{k-1}{2}$ であるから

$$ \frac{a_m + k}{3} \leqq \frac{\frac{k-1}{2} + k}{3} = \frac{3k - 1}{6} = \frac{k}{2} - \frac{1}{6} $$

したがって

$$ a_{m+1} \leqq \frac{k}{2} - \frac{1}{6} < \frac{k}{2} $$

両辺を $2$ 倍すると $2a_{m+1} < k$ となる。$a_{m+1}$ と $k$ はともに整数であるから

$$ 2a_{m+1} \leqq k - 1 $$

すなわち $a_{m+1} \leqq \frac{k-1}{2}$ となり、$n=m+1$ のときも成り立つ。以上より、すべての自然数 $n$ に対し $a_n \leqq \frac{k-1}{2}$ が示された。

次に、すべての自然数 $n$ に対し $a_n \leqq a_{n+1}$ であることを示す。前半で示した $a_n \leqq \frac{k-1}{2}$ より、$2a_n \leqq k-1$ すなわち $k \geqq 2a_n + 1$ が成り立つ。これを用いると

$$ a_{n+1} = \left[ \frac{a_n + k}{3} \right] \geqq \left[ \frac{a_n + (2a_n + 1)}{3} \right] = \left[ a_n + \frac{1}{3} \right] $$

$a_n$ は整数であるから、$\left[ a_n + \frac{1}{3} \right] = a_n$ となる。したがって、$a_{n+1} \geqq a_n$ が成り立つ。（証明終）

(3)

$a_n = a_{n+1}$ ならば、 $m \geqq n$ であるすべての整数 $m$ に対し $a_m = a_n$ であることを $m$ に関する数学的帰納法で示す。

(i)

$m=n, n+1$ のときは、仮定より $a_n = a_{n+1}$ であるから成り立つ。

(ii)

$m=l$ ($l \geqq n+1$) のとき、$a_l = a_n$ が成り立つと仮定する。

$m=l+1$ のとき、漸化式より

$$ a_{l+1} = \left[ \frac{a_l + k}{3} \right] $$

仮定より $a_l = a_n$ であるから

$$ a_{l+1} = \left[ \frac{a_n + k}{3} \right] = a_{n+1} = a_n $$

よって $m=l+1$ のときも成り立つ。以上より、$n$ 以上のすべての整数 $m$ に対し $a_m = a_n$ である。（証明終）

このときの $a_n$ の値を求める。 $a_n = a_{n+1} = \left[ \frac{a_n + k}{3} \right]$ である。ガウス記号の定義 $[x] \leqq x < [x] + 1$ より

$$ a_n \leqq \frac{a_n + k}{3} < a_n + 1 $$

各辺を $3$ 倍して整理すると

$$ 3a_n \leqq a_n + k < 3a_n + 3 $$

$$ 2a_n \leqq k < 2a_n + 3 $$

これより $k - 3 < 2a_n \leqq k$ を得る。さらに、(2) で示した不等式より $2a_n \leqq k - 1$ であるから、これを合わせると

$$ k - 3 < 2a_n \leqq k - 1 $$

すなわち

$$ k - 2 \leqq 2a_n \leqq k - 1 $$

となる。$2a_n$ は整数であるから、$2a_n = k-2$ または $2a_n = k-1$ のいずれかである。

・$k$ が偶数のとき

$k-1$ は奇数となるため、$2a_n$ と等しくなることはない。よって $2a_n = k-2$ となり

$$ a_n = \frac{k-2}{2} $$

・$k$ が奇数のとき

$k-2$ は奇数となるため、$2a_n$ と等しくなることはない。よって $2a_n = k-1$ となり

$$ a_n = \frac{k-1}{2} $$

これらはガウス記号を用いてまとめて $a_n = \left[ \frac{k-1}{2} \right]$ と表すこともできる。

解説

ガウス記号の扱いに慣れているかを問う良問です。ガウス記号の処理の基本は「不等式による評価」です。値が整数であることを強く意識し、単なる実数の不等式から整数の不等式へと議論を一段階引き上げることが重要になります。本問の (2) の証明において、$2a_{m+1} < k$ から $2a_{m+1} \leqq k - 1$ を導く部分は、両辺が整数であることに着目した論理の飛躍のないスマートな変形です。(3) においても同様に、不等式の両端の整数値の幅を絞ることで、とり得る値を特定しています。