東京大学 1983年度 前期日程 第2次学力試験理系数学 第2問

(1)
既出の項と異なること、ならびに
(2)
以前の項の部分和で表せないことを同時に確認する。結論は$$a_n=2^{n-1}$$である。これを数学的帰納法で示す。

$a_1=1=2^0$ である。ある $n\geqq 2$ について$$a_1,a_2,\dots ,a_{n-1}=1,2,4,\dots ,2^{n-2}$$であると仮定する。各 $2^k$ を使うか使わないかを選べば、2進表示により$$0,1,2,\dots ,2^{n-1}-1$$のすべてが、以前の項を重複なく選んだ和として一意に表される。したがって $2^{n-1}$ より小さい自然数は条件を満たさない。

一方、以前の全項の和は$$1+2+4+\cdots +2^{n-2}=2^{n-1}-1$$であるから、$2^{n-1}$ は以前の項の和では表せず、既出の項でもない。よって条件を満たす最小の自然数は $2^{n-1}$ である。帰納法により、すべての $n$ で$$a_n=2^{n-1}$$が成り立つ。

既存項の部分和は $0$ から「次の項の1つ前」までを埋める

最初の $n$ 項から作れる部分和が、隙間のない区間 $0,1,\dots ,S_n$ になることに注目する。次の最小許容値は常に $S_n+1$ であり、それを加えると部分和区間がちょうど2倍に延びる。この和の漸化式を解く。

(1)
既出項との相違と、
(2)
部分和で表せないことを、部分和区間を用いて同時に扱う。最初の $n$ 項の和を$$S_n=a_1+a_2+\cdots +a_n$$とする。さらに、最初の $n$ 項から作れる部分和が$$0,1,2,\dots ,S_n$$をすべて含むことを同時に示す。

$n=1$ では $a_1=1$、$S_1=1$ で、部分和は $0,1$ である。いま $0$ から $S_{n-1}$ までがすべて作れるとする。このとき $1,2,\dots ,S_{n-1}$ は次の項に選べない。一方、$S_{n-1}+1$ は以前の全項の和より大きいので作れず、既出でもない。したがって$$a_n=S_{n-1}+1.$$新しい項 $a_n$ を使わない部分和は $0$ から $S_{n-1}$、使う部分和は$$S_{n-1}+1,S_{n-1}+2,\dots ,2S_{n-1}+1$$となる。よって隙間なく $0$ から $S_n$ まで作れ、$$S_n=2S_{n-1}+1,S_1=1.$$したがって $S_n=2^n-1$ であり、$$a_n=S_n-S_{n-1}=2^{n-1}$$を得る。