位取り記数法の性質の良さ

(1)$\displaystyle \sum_{k=M}^Na_kD^{(k)}\neq 0$より$\displaystyle\sum_{k=M}^Na_k\neq 0$だから,
$\displaystyle \sum_{k=M}^Na_kD^{(k)}\geq \sum_{k=M}^Na_kD^{(M)}\geq D^{(M)}.\ \square$
(2)$(\Rightarrow)$ は$D^{(K+1)}$の位の値を比較すれば定義より明らか.
$(\Leftarrow)$について,$\displaystyle \sum_{k=0}^{N}a_kD^{(k)},\sum_{k=0}^{N}a'_kD^{(k)}$
で$a_N< a'_N$のとき,
$\displaystyle \sum_{k=0}^{N}a'_kD^{(k)}-\sum_{k=0}^{N}a_kD^{(k)}$
$\displaystyle=(a'_N-a_N)D^{(N)}+\sum_{k=0}^{N-1}(a'_k-a_k)D^{(k)}$
$\displaystyle \geq D^{(N)}-\sum_{k=0}^{N-1}A_kD^{(k)}>0$だから,
$\displaystyle \sum_{k=0}^{N}a_kD^{(k)}<\sum_{k=0}^{N}a'_kD^{(k)}.\ \square$

帰納法を用いて示す.
整数$1\leq n\leq A_0$は$1D^{(0)},\ldots ,A_0D^{(0)}$と表記できるから一意性より
\begin{equation} D^{(1)}\geq A_0D^{(0)}+1. \end{equation}
また,完全性より整数$A_0D^{(0)}+1$を$\displaystyle \sum_{k=0}^{N}a_kD^{(k)} $と表記すると
$\displaystyle A_0D^{(0)}+1=\sum_{k=0}^{N}a_kD^{(k)}$
$\displaystyle=a_0D^{(0)}+\sum_{k=1}^{N}a_kD^{(k)}$となり,左辺は正だから補題1の(1)より
$\displaystyle (A_0-a_0)D^{(0)}+1=\sum_{k=1}^{N}a_kD^{(k)}\geq D^{(1)}.$
よって
$\displaystyle A_0D^{(0)}+1\leq D^{(1)}\leq (A_0-a_0)D^{(0)}+1.$
左辺と右辺を比較すると$a_0=0$となるから,
\begin{equation} D^{(1)}=A_0D^{(0)}+1. \end{equation}
すなわち$K=0$での成立を示せた.
このとき,整数$1\leq n \leq S^{(1)}$はそれぞれ,
$1D^{(0)},\ldots ,A_0D^{(0)},1D^{(1)},$
$1D^{(0)}+1D^{(1)},\ldots,A_0D^{(0)}+1D^{(1)},2D^{(1)},$
$1D^{(0)}+2D^{(1)},\ldots,A_0D^{(0)}+A_1D^{(1)}$
と表記できる.同様に整数$0\leq K'< K$で
\begin{equation} D^{(K'+1)}= S^{(K')}+1 \end{equation}
が成立すると仮定すると,整数$1\leq n \leq S^{(K)}$はそれぞれ
$\displaystyle 1D^{(0)},\ldots , \displaystyle\sum_{k=0}^{K}a_kD^{(k)} ,\ldots, \displaystyle\sum_{k=0}^{K}A_kD^{(k)}$
と表記できる.よって一意性から
\begin{equation} D^{(K+1)}\geq S^{(K)}+1 \end{equation}
が従い,完全性から$\displaystyle S^{(K)}+1=\sum_{k=0}^{N}a_kD^{(k)}$
と表記すると,補題1の(1)より
$\displaystyle\sum_{k=0}^{N}a_kD^{(k)} =a_0D^{(0)}+\cdots+a_KD^{(K)}+\sum_{k=K+1}^{N}a_kD^{(k)}$
だから
$\displaystyle\sum_{k=0}^{K}(A_k-a_k)D^{(k)}+1=\sum_{k=K+1}^{N}a_kD^{(k)}\geq D^{(K+1)}$
となる.従って,
\begin{equation} S^{(K)}+1\leq D^{(K+1)}\leq \sum_{k=0}^{K}(A_k-a_k)D^{(k)}+1 \end{equation}
が従い,$a_0=\cdots=a_K=0$であり,
\begin{equation} D^{(K+1)}=S^{(K)}+1 \end{equation}
となり,$K$での成立が確かめられ,帰納法によって補題が示された. $\square$

(1)補題2より,$D^{(K+1)}= S^{(K)}+1>S^{(K)}$だから補題1の(2)より単調性を満たす.$\blacksquare$
(2)$\displaystyle \sum_{k=0}^{N}a_kD^{(k)} =\sum_{k=0}^{N'}a'_kD^{(k)}$とすると,補題1の(2)より$N=N'$.よって$a_N\leq a'_N$とすると,
$\displaystyle (a'_N-a_N)D^{(N)}=\sum_{k=0}^{N-1}(a_k-a'_k)D^{(k)}$
$\displaystyle\leq \sum_{k=0}^{N-1}A_kD^{(k)}=S^{(N-1)}$
となるから単調性より$a'_N-a_N=0$すなわち$a'_N=a_N$であり,
$\displaystyle \sum_{k=0}^{N-1}a_kD^{(k)} =\sum_{k=0}^{N-1}a'_kD^{(k)}$
となる.同様の議論をすれば$k=1,\ldots N$で$a_k=a_k'$となり一意性を満たすことが従う.$\blacksquare$

補題2を用いて帰納法で示す.
$K=1$のとき,$D^{(1)}=A_0D^{(0)}+1=A_0+1.$
$\displaystyle D^{(K)}=\prod_{k=0}^{K-1}(A_k+1)$を仮定すると,
$\displaystyle D^{(K+1)}=\sum_{k=0}^{K}A_kD^{(k)}+1$
$=1+A_0+A_1(A_0+1)+\cdots + A_K(A_{K-1}+1)\cdots(A_0+1)$
$=(A_0+1)+A_1(A_0+1)+\cdots + A_K(A_{K-1}+1)\cdots(A_0+1)$
$=(A_1+1)(A_0+1)+\cdots + A_K(A_{K-1}+1)\cdots(A_0+1)$
$=\cdots =(A_K+1)(A_{K-1}+1)\cdots(A_0+1)$
$\displaystyle =\prod_{k=0}^{K-1}(A_k+1).\blacksquare$