n桁の長さのビット列は2<sup>n</sup>種類ある

　上の命題が正しいことを、再帰的証明法(=数学的帰納法)を用いて証明する。

[1] 1桁の場合

1桁のビット列(?)には × と ○ との2種類がある。一方で、

　2ⁿ = 2

このように、1桁の場合については、上の命題は成り立つ。

[2] 2桁以上の場合

k桁のビット列には2^k種類があることが明らかになっているとする。

k＋1桁のビット列は、k桁のビット列のそれぞれの右端に新しいビットとして○か×のどちらかがつけ加えられることによって作られる。もとのビット列は2^k種類あって、そのそれぞれについて×と○との2種類のビットのどちらかをつけ加えることができるので、k＋1桁のビット列の種類の数は、

　2^k・2 = 2^k＋1

となる。
[1]と[2]とから、n=1,2,3,...のすべてに対して、命題：

　n桁の長さのビット列は2ⁿ種類である

が成り立つことが分る。

桁数	ビット列	種類
0桁	(空列)	1種類
1桁	× ○	2種類
2桁	×× ×○ ○× ○○	4種類
3桁	××× ××○ ... ○○○	8種類
4桁	×××× ×××○ ... ○○○○	16種類
...
8桁		256種類
...
16桁		65536種類
...