数遊び

「nを自然数として
1から2^(n+1)-1 までの全ての整数は
1,2,4,…,2^nからなるn個の数の集合の
その要素の和の組み合わせで表現される
ただし同じ要素を重複して選ぶことはしない」•••@

nを自然数とし、
U(n)を1,2,4,…,2^nのn個の整数を要素にもつ集合とする
(1)n=1のとき
U(1)={1,2}であり
1=1
2=2
3=1+2 であるから
1から3までの全ての整数はU(1)から重複するを許すことなく選んだ要素の和の組み合わせとして表現される

(2)n=kのとき　@が成立していると仮定する

このときn=k+1を考える
U(k+1)={1,2,4,…,2^(k+1)}である
さらにU(k+1)=U(k)+{2^(k+1)}が成立

今、明らかにU(k)はU(k+1)に含まれており、仮定よりU(k)から重複を許すことなく選んだ要素の和の組み合わせとして、1から2^(k+1)-1までの全ての整数を表現できるため、U(k+1)から重複を許すことなく選んだ要素の和の組み合わせとして、1から2^(k+1)-1までの全ての整数を表現できる

また2^(k+1)は定義から明らかにU(k+1)の要素である

さらに2^(k+1)+1から2^(k+2)-1までの全ての整数は、仮定よりU(k)から重複を許すことなく選んだ要素の和の組み合わせとして表現される1から2^(k+1)-1までの全ての整数に等しく2^(k+1)を加えた数である。そしてこのときU(k+1)=U(k)+{2^(k+1)} であることから、2^(k+1)+1から2^(k+2)-1までの全ての整数も、U(k+1)から重複を許すことなく選んだ要素の和の組み合わせとして表現されたと言える。

したがって1から2^(k+2)-1までの全ての整数は、U(k+1)から重複を許すことなく選んだ要素の和の組み合わせとして表現される。
すなわちn=k+1でも@が成立する

(1),(2)より全ての自然数nにおいて@が成立する