（１）ｎ＝１のとき、
　　　　　Ｕ＝｛１｝の部分集合は、φまたは｛１｝の２つ
　　　　　左辺＝1Ｃ0＋1Ｃ1＝１＋１＝２＝２^1＝右辺
（２）ｎ＝ｋのとき次が成り立つと仮定して、
　　　　　Ｕ＝｛１，２，………，ｋ｝の部分集合は、全部で２^k　個ある。
　　　　　左辺＝kＣ0＋kＣ1＋………＋kＣk＝２^k＝右辺
　　　ｎ＝ｋ＋１のとき、
　　　　　Ｕ＝｛１，２，………，ｋ，ｋ＋１｝の部分集合は、
　　　　　左辺＝(k+1)Ｃ0＋(k+1)Ｃ1＋………＋(k+1)Ｃk＋(k+1)Ｃ(k+1)
　　　　　　　　　　　　　^^^^^^^^
　　　　　　　　＜公式　nＣ(k-1)＋nＣk＝(n+1)Ｃkより＞

　　　　　　　＝１＋（kＣ0＋kＣ1）＋（kＣ1＋kＣ2）＋……
　　　　　　　　　　^^^^^^^^^^^^^　　………＋｛kＣ(k-1)＋kＣk｝＋１
　　　　　　　＝kＣ0＋（kＣ0＋kＣ1）＋（kＣ1＋kＣ2）＋……
　　　　　　　　　　　　　　　　　　　………＋｛kＣ(k-1)＋kＣk｝＋kＣk
　　　　　　　＝２（kＣ0＋kＣ1＋………kＣk）
　　　　　　　＝２・２^k
　　　　　　　＝２^(k+1)
　　　　　　　＝右辺
　　　　　したがって、全部で２^(k+1)　個ある。
（１）（２）より、自然数ｎに対して、成り立つ。