今、我々はGrahamの定理の証明を理解することを目標としています:
integers.hatenablog.com
この記事では証明のための準備として、数列の完全性に関するBrownの判定法を紹介します。
定義 正の実数からなる数列に対し、集合をで定める(の相異なる項の有限和として表される数全体のなす集合)。このとき、が完全であるとは、任意の自然数がの元であるときにいう*1。
定理 (Brownの判定法) を初項がの自然数からなる非減少数列とする。 このとき、が完全であるための必要十分条件は、任意の自然数に対してが成り立つことである。
証明. が完全であると仮定する。ある番号が存在して
であったと仮定する。このとき、の非減少性と完全性からはからを用いた和で表されるはずである。しかしながら、そのような和の最大値であるよりはでかいと言っているので、はの元ではないことになってが完全であるという仮定に矛盾する。
逆を示すには次の主張を示せばよい:
主張 自然数列が任意の非負整数に対してを満たすと仮定する*2。を自然数とする。このとき、より小さい任意の自然数は、或るを用いてと書ける。
に関する帰納法で証明する。のときはなので、より成立することがわかる。で成立すると仮定してのときに示そう。帰納法の仮定により、
なるについて考察すればよい。主張の問題文にある仮定より、
である。のときは、そのについて示したいことが成り立っている。そうでない場合は
となるので、帰納法の仮定によって、あるが存在して
と書ける。すなわち、とすれば、
を得る。これで定理の証明が全て完了する。 Q.E.D.
おまけ
Fibonacci数列を考えましょう。89:フィボナッチ数 - INTEGERS
これは初項がの非減少自然数列です。また、定義から容易に確認できるように、任意の自然数に対して
が成り立ちます。よって、Brownの判定法によりFibonacci数列は完全であることが分かります。すなわち、次が成り立ちます:
系 任意の自然数は相異なるFibonacci数の有限個の和として表すことができる。
例えば、今日は6月24日ですが、
です()。 cf. Zeckendorf表示.