
Induction
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^n1 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^n1.
(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 bitstrings 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