京都大学 2013年度理系数学第2問解答・解説

問題

$N$ を2以上の自然数とし， $a_{n}$ $(n = 1, 2, \dots)$ を次の性質(i)，(ii)をみたす数列とする．

(i) $a_{1} = 2^{N} - 3$ ．

(ii) $n = 1, 2, \dots$ に対して，
$a_{n}$ が偶数のとき $a_{n + 1} = \frac{a _{n}}{2}$ ， $a_{n}$ が奇数のとき $a_{n + 1} = \frac{a _{n} - 1}{2}$ ．

このときどのような自然数 $M$ に対しても

n = 1 \sum M a_{n} ≦ 2^{N + 1} - N - 5

が成り立つことを示せ．

出典：京都大学 2013年度前期日程第2次学力試験理系第2問

方針

偶数・奇数の場合分けはどちらも $a_{n + 1} = ⌊ a_{n} /2 ⌋$ を表している。したがって2進法で見ると、各ステップで右端の1桁を消す操作である。初項 $2^{N} - 3$ の2進表示は、 $2^{1}$ の位だけが0で、 $2^{0}$ と $2^{2}, \dots, 2^{N - 1}$ の位が1である。各桁の1が、右へずれながら消えるまで総和にどれだけ寄与するかを足し上げ、任意の有限和は全体和以下であることを示す。

解答

条件(ii)は、 $a_{n}$ が偶数でも奇数でも $a_{n + 1} = [\frac{a _{n}}{2}]$ を表している。すなわち、 $a_{n}$ を2で割った商を次の項にしている。これは2進法でいうと、右端の桁を1つ消す操作である。

初項は $a_{1} = 2^{N} - 3 = (2^{N} - 1) - 2$ である。 $2^{N} - 1$ は2進法で下から $N$ 桁がすべて1の数であり、そこから2を引くので、 $2^{1}$ の位だけが0、 $2^{0}$ の位と $2^{2}, 2^{3}, \dots, 2^{N - 1}$ の位が1になる。

ある $2^{j}$ の位にある1は、右端へ移動して消えるまで、各項の和に $2^{j} + 2^{j - 1} + \dots + 2 + 1 = 2^{j + 1} - 1$ だけ寄与する。したがって、数列が0になるまでのすべての項の和は $(2^{1} - 1) + \sum_{j = 2}^{N - 1} (2^{j + 1} - 1)$ である。ここで $N = 2$ のときは和 $\sum_{j = 2}^{N - 1}$ は空和として0と考えればよい。

これを計算すると $(2^{1} - 1) + \sum_{j = 2}^{N - 1} (2^{j + 1} - 1) = 1 + (2^{3} + 2^{4} + \dots + 2^{N}) - (N - 2)$ $= 1 + (2^{N + 1} - 8) - (N - 2) = 2^{N + 1} - N - 5$ である。

各 $a_{n}$ は0以上であり、 $M$ までの部分和は、0になるまでの全体の和を超えない。したがって、どのような自然数 $M$ に対しても $\sum_{n = 1}^{M} a_{n} ≦ 2^{N + 1} - N - 5$ が成り立つ。

京都大学 2013年度理系数学 第2問

問題

方針

解答

京都大学 2013年度
理系数学第2問