Consider the set D0 consisting of those strings in C0 with the leading 0 removed. In our example above, D0 contains the strings 00 and 11. We claim that D0 cannot have two strings differing in only one bit. The reason is that if there are two such strings — say a1a2 · · · an and b1b2 · · · bn — then restoring their leading 0’s gives us two strings in C0, 0a1a2 · · · an and 0b1b2 · · · bn, and these strings would differ in only one position as well. But strings in C0 are also in C, and we know that C does not have two strings that differ in only one position. Thus, neither does D0, and so D0 is an error detecting set. Now we can apply the inductive hypothesis to conclude that D0, being an error-detecting set with strings of length n, has at most 2n−1 strings. Thus, C0 has at most 2n−1 strings.

We can reason similarly about the set C1. Let D1 be the set of strings in C1, with their leading 1’s deleted. D1 is an error-detecting set with strings of length n, and by the inductive hypothesis, D1 has at most 2n−1 strings. Thus, C1 has at most 2n−1 strings. However, every string in C is in either C0 or C1. Therefore, C has at most 2n−1 + 2n−1 , or 2n strings.

We have proved that S(n) implies S(n+ 1), and so we may conclude that S(n) is true for all n ≥ 1. We exclude n = 0 from the claim, because the basis is n = 1, not n = 0. We now see that the error-detecting sets constructed by parity check are as large as possible, since they have exactly 2n−1 strings when strings of n bits are used.