トップ› 東京大学› 1983年› 理系第2問

東京大学 1983年理系第2問解説

方針・初手

まずは $n=1, 2, 3, 4$ 程度の具体的な値を求めて、$a_n$ の規則性を推測する。その後、推測した一般項が正しいことを数学的帰納法を用いて証明する。このとき、$a_n$ の一般項だけでなく「それまでの項をいくつか選んで作られる和が、どの範囲の自然数をすべて網羅するか」という命題も合わせて帰納法の仮定に組み込むことがポイントである。

解法1

$a_1 = 1$ である。

$n=2$ のとき、条件 (1), (2) より $a_2 \neq 1$ であり、これを満たす最小の自然数は $2$ であるから $a_2 = 2$ となる。

$n=3$ のとき、$a_1, a_2$ から作られる和は $1+2=3$ であり、条件より $a_3 \neq 1, 2, 3$ を満たす最小の自然数は $4$ であるから $a_3 = 4$ となる。

$n=4$ のとき、$a_1, a_2, a_3$ から作られる和は $1+2=3, 1+4=5, 2+4=6, 1+2+4=7$ であり、これらと各項を含めると $1, 2, 3, 4, 5, 6, 7$ となる。条件より $a_4$ はこれらと異なる最小の自然数であるから $a_4 = 8$ となる。

これより、$a_n = 2^{n-1}$ であると推測できる。この推測を含め、以下の命題 $P(n)$ がすべての自然数 $n$ について成り立つことを数学的帰納法で示す。

命題 $P(n)$ : 「$a_n = 2^{n-1}$ であり、$a_1, a_2, \cdots, a_n$ のうちから重複なく1個以上の項を取り出して作られる和全体の集合は、$1$ 以上 $2^n-1$ 以下のすべての自然数からなる」

(i)

$n=1$ のとき

$a_1 = 1 = 2^0$ であり、$a_1$ から作られる和は $1$ のみである。これは $1$ 以上 $2^1-1 = 1$ 以下のすべての自然数であるから、$P(1)$ は成り立つ。

(ii)

$n=k$ （$k$ は自然数）のとき、$P(k)$ が成り立つと仮定する。

すなわち、$a_k = 2^{k-1}$ であり、$a_1, a_2, \cdots, a_k$ から作られる和は $1$ 以上 $2^k-1$ 以下のすべての自然数を網羅しているとする。

$n=k+1$ のときを考える。 $a_{k+1}$ は、条件 (1), (2) により $a_1, \cdots, a_k$ のいずれとも異なり、かつそれらの和のいずれとも異なる最小の自然数である。帰納法の仮定より、$a_1, \cdots, a_k$ までの項およびその和として現れる値は $1, 2, \cdots, 2^k-1$ のすべての自然数である。したがって、これらに含まれない最小の自然数は $2^k$ であり、次のように決まる。

$$ a_{k+1} = 2^k = 2^{(k+1)-1} $$

次に、$a_1, a_2, \cdots, a_{k+1}$ のうちから重複なく項を取り出して作られる和について考える。その和は、以下の3つの場合に分けられる。

(ア)

$a_{k+1}$ を含まない場合

和は $a_1, \cdots, a_k$ から作られる和であり、仮定より $1$ 以上 $2^k-1$ 以下のすべての自然数となる。

(イ)

$a_{k+1}$ のみの場合

和は $2^k$ となる。

(ウ)

$a_{k+1}$ と $a_1, \cdots, a_k$ の一部を含む場合

和は $2^k + (\text{1 以上 } 2^k-1 \text{ 以下の自然数})$ となり、$2^k+1$ 以上 $2^k + 2^k - 1 = 2^{k+1}-1$ 以下のすべての自然数となる。

（ア）, （イ）, （ウ）を合わせると、$a_1, a_2, \cdots, a_{k+1}$ から作られる和全体の集合は、$1$ 以上 $2^{k+1}-1$ 以下のすべての自然数となる。よって、$n=k+1$ のときも $P(k+1)$ は成り立つ。

（i）, （ii）より、すべての自然数 $n$ について命題 $P(n)$ は成り立ち、$a_n = 2^{n-1}$ である。

解説

実験を行うことで数列の規則性を発見し、数学的帰納法を用いて厳密に証明する典型的な整数・数列問題である。帰納法の仮定を設定する際、$a_k$ の一般項だけを仮定しても $a_{k+1}$ の値を確定させることができない。そのため、「作られる和が特定の連続する自然数をすべて覆い尽くす」という性質まで含めて命題を設定し、強い帰納法として回していくのが最大のポイントである。これは、任意の自然数が2の累乗の和（2進数展開）で一意に表せるという事実を背景としている。