問題
数列において，であり，に対しては，次の条件(1)，(2)をみたす自然数のうち最小のものであるという．
(1) は，のどの項とも異なる．
(2) のうちから重複なくどのように項を取り出しても，それらの和がに等しくなることはない．
このとき，をで表し，その理由を述べよ．
出典：東京大学 1983年度 前期日程 第2次学力試験 理系 第2問
方針
既に選ばれた項から作れる部分和の集合を調べる。 まで選ばれていると仮定すると、各項を使うか使わないかで から までの整数がすべて作れる。したがって、既出でも部分和でもない最小の自然数は になる。これを帰納法で示す。
解答
答は である。
(1)
まず なので、 では成り立つ。
次に、ある に対して が であると仮定する。
(2)
これらの項から重複なくいくつかを取り出して和を作ることは、各 を使うか使わないかを選ぶことと同じである。したがって、作れる和は のすべてである。これは2進法の表示が、各桁を または として一意に決まることから分かる。
よって、自然数 はすべて、すでに現れている項であるか、または以前の項の和として表される。したがって条件 (1)、(2) を満たす自然数は、少なくとも 以上でなければならない。
一方、 はまだ項として現れておらず、以前の項の和でも表せない。以前の項をすべて足しても だからである。
したがって、条件を満たす最小の自然数は である。帰納法により、すべての について が成り立つ。