インテジャーズ

INTEGERS

数、特に整数に関する記事。

数列の完全性に関するBrownの判定法

今、我々はGrahamの定理の証明を理解することを目標としています:
integers.hatenablog.com

この記事では証明のための準備として、数列の完全性に関するBrownの判定法を紹介します。

定義 正の実数からなる数列S:=\{a_n\}_{n=1}^{\infty}に対し、集合P(S)
P(S):=\{\sum_{k=1}^{\infty}\varepsilon_ka_k \mid \varepsilon_k \in \{0, 1\}, \text{有限個の}k\text{を除いて}\varepsilon_k=0\}
で定める(Sの相異なる項の有限和として表される数全体のなす集合)。このとき、S完全であるとは、任意の自然数nP(S)の元であるときにいう*1

定理 (Brownの判定法) S:=\{a_n\}を初項がa_1=1の自然数からなる非減少数列とする。 このとき、Sが完全であるための必要十分条件は、任意の自然数kに対して\displaystyle a_{k+1}\leq 1+\sum_{i=1}^ka_iが成り立つことである。

証明. Sが完全であると仮定する。ある番号n_0が存在して

\displaystyle a_{n_0+1} > a_{n_0+1}-1 > \sum_{i=1}^{n_0}a_i

であったと仮定する。このとき、Sの非減少性と完全性からa_{n_0+1}-1a_1からa_{n_0}を用いた和で表されるはずである。しかしながら、そのような和の最大値である\sum_{i=1}^{n_0}a_iよりa_{n_0+1}-1はでかいと言っているので、a_{n_0+1}-1P(S)の元ではないことになってSが完全であるという仮定に矛盾する。

逆を示すには次の主張を示せばよい:

主張 自然数列S:=\{a_n\}が任意の非負整数kに対して a_{k+1}\leq 1+\sum_{i=1}^ka_iを満たすと仮定する*2jを自然数とする。このとき、1+\sum_{i=1}^ja_iより小さい任意の自然数nは、或る\varepsilon_1, \dots, \varepsilon_j \in \{0, 1\}を用いてn=\sum_{i=1}^j\varepsilon_ia_iと書ける。

jに関する帰納法で証明する。j=1のときは1+a_1=2なので、1=1 \cdot a_1より成立することがわかる。jで成立すると仮定してj+1のときに示そう。帰納法の仮定により、

\displaystyle 1+\sum_{i=1}^ja_i \leq n < 1+\sum_{i=1}^{j+1}a_i

なるnについて考察すればよい。主張の問題文にある仮定より、

\displaystyle n-a_{j+1} \geq 1+\sum_{i=1}^ja_i-a_{j+1} \geq 0

である。n-a_{j+1}=0のときは、そのnについて示したいことが成り立っている。そうでない場合は

\displaystyle 0 < n-a_{j+1} < 1+\sum_{i=1}^ja_j

となるので、帰納法の仮定によって、ある\varepsilon_1, \dots, \varepsilon_j \in \{0, 1\}が存在して

\displaystyle n-a_{j+1} = \sum_{i=1}^j\varepsilon_ia_i

と書ける。すなわち、\varepsilon_{j+1}:=1とすれば、

\displaystyle n= \sum_{i=1}^{j+1}\varepsilon_ia_i

を得る。これで定理の証明が全て完了する。 Q.E.D.

おまけ

Fibonacci数列\{F_n\}を考えましょう。89:フィボナッチ数 - INTEGERS

これは初項がF_1=1の非減少自然数列です。また、定義から容易に確認できるように、任意の自然数kに対して

\displaystyle F_{k+1} < F_{k+2} = 1+\sum_{i=1}^kF_i

が成り立ちます。よって、Brownの判定法によりFibonacci数列は完全であることが分かります。すなわち、次が成り立ちます:

任意の自然数は相異なるFibonacci数の有限個の和として表すことができる。

例えば、今日は6月24日ですが、

624=F_1+F_7+F_{15}

です(F_1=1, F_7=13, F_{15}=610)。 cf. Zeckendorf表示.

*1:定義より0 \in P(S)である事に注意。以降は、P(S)の元であるかどうかを判定することを考えるため、「0Sの項の有限個(0個)の和として表される」と考えておくと良いです。この意味で、Grahamの定理に現れる集合は

\displaystyle \left[ 0, \frac{\pi^2}{6}-1 \right) \cup \left[ 1, \frac{\pi^2}{6} \right) .
となります(Wikipediaの『エジプト式分数』やGrahamの論文にはこれが書いてありますが、今述べたような理由で0を含めています)。

*2:k=0のときは右辺の和は0とみなす。これはa_1=1を意味する。