正の整数は2のべき乗の和で一意的に表せる．

　マグロウヒル大学演習シリーズ 微積分(上)の問題39の別解を載せる．

問39

　任意の正の整数$P$は，$a_i$を0か1として，$P = a_0 2^{n} + a_1 2^{n-1} + a_2 2^{n-2} + \cdots + a_n$ の形に，一意的に表されることを証明せよ．

2のべき乗の和で表せられること．

　正の整数$P$が$P=a_0 2^{n} + a_1 2^{n-1} + \cdots + a_n$(2のべき乗の和)の形で表されることを， 正の整数による帰納法により示す．

　$P=0$のとき，$n=0$において，$a_0=0$として表せられる．

　$P=1$のとき，$n=0$において，$a_0=1$として表せられる．

　$P=2$のとき，$n=1$において，$a_0=1, a_1=0$として，$P = a_0 2^{1} + a_1$と表せられる．

　$P \leq k（kは正の整数）$のとき，2のべき乗の和として表せられると仮定する．$P=k+1$のときを考える． $k+1$を2で割った余りを$a_{n+1}$，商を$p$とすると，$k+1=2p+a_{n+1}$．

　$pはk以下$なので，仮定より$p$は2のべき乗の和の形で表せられる．よって，$2p + a_{n+1}$は2のべき乗の和の形で表せられる． つまり，$P$は2のべき乗の和の形で表せられる．

　以上により，帰納法で正の整数$P$が2のべき乗の和の形で表せられることを示した．

一意的に表せられること．

　正の整数$P$を以下の2通りに表せられるとする．

$$\begin{align} P &= a_n 2^{n} + a_{n-1} 2^{n-1} + \cdots + a_0 \\ &= b_n 2^{n} + b_{n-1} 2^{n-1} + \cdots + b_0 \end{align}$$

　$P$を2で割った余りは(1)，(2)で等しいので，$a_0 = b_0$．$P$を2で割った商を$P_1$とすると， この$P_1$を2で割った余りは(1)，(2)で等しいので，$a_1 = b_1$．以降，同様にすると， $a_i = b_i (i=0,1, \cdots, n)$である．したがって，(1)，(2)は等しい， すなわち$P$は一意的に2のべき乗の和で表せる．