For n ∈ N let Bn be the set of all n-digit binary numbers. For example B3 = {000, 001, 010, 100, 011, 101, 110, 111}. (a) Show that |Bn| = 2^n .

Question

Mathematical proofs

Method to be used is mathematical induction

Answer 1

The only digits available to form binary numbers are 0 and 1. For single digit binaries there are 2 in the set B1; for 2-digit binaries there are 4 because there are 4 ways (2*2) to arrange 0's and 1's in pairs. 

An ordered set of binary integers starts at 000...0 and ends with 111...1 for n-digit binaries.

The set of n-digit binaries can be expressed as the continuous range 000...0 000...01 to 111...11. These are the integers 0, 1 to 2^n - 1.

So the set contains 2^n elements when 0 is included. Therefore |Bn|=2^n.