Here is an outline of an inductive proof that if C is any collection of unique bit strings of length n (a bit string of length n is a sequence of 0's and 1's of length n) such that no pair of bit strings in C differs in exactly one position, then C contains at most 2^n-1 strings. It is up to you to ll it in.

Proof:

Let n be an arbitrary positive integer, and let C(n) be a collection of unique bit strings of length n such that no pair of bit strings in C(n) differs in exactly one position. We show that the number of

elements in C(n) is at most 2^n-1.

(write the inductive hypothesis)

We consider two cases: either n = 1 or n >= 2.

Suppose n = 1.

(fill in your solution here)

Suppose n >= 2, and partition the bit-strings in C(n) into two groups: those which end in 0 and and those which end in 1.

(fill in the rest of the solution here)

Im working on a sample exam to study for a final, and stuck on this question. Any help is appreciated.

Thanks