No two sequences of bits that each have even parity can differ in only one position. For if two such bit sequences differ in exactly one position, then one has exactly one more 1 than the other. Thus, one sequence must have odd parity and the other even parity, contradicting our assumption that both have even parity. We conclude that addition of a parity bit to make the number of 1’s even serves to create an error-detecting code for characters. The parity-bit scheme is quite “efficient,” in the sense that it allows us to transmit many different characters. Note that there are 2n different sequences of n bits, since we may choose either of two values (0 or 1) for the first position, either of two values for the second position, and so on, a total of 2× 2 × · · ·× 2 (n factors) possible strings. Thus, we might expect to be able to represent up to 28 = 256 characters with eight bits. However, with the parity scheme, we can choose only seven of the bits; the eighth is then forced upon us.

We can thus represent up to 27 , or 128 characters, and still detect single errors. That is not so bad; we can use 128/256, or half, of the possible 8-bit codes as legal codes for characters, and still detect an error in one bit. Similarly, if we use sequences of n bits, choosing one of them to be the parity bit, we can represent 2n−1 characters by taking sequences of n−1 bits and prefixing the suitable parity bit, whose value is determined by the other n − 1 bits.

Since there are 2n sequences of n bits, we can represent 2n−1/2 n, or half the possible number of characters, and still detect an error in any one of the bits of a sequence. Is it possible to detect errors and use more than half the possible sequences of bits as legal codes? Our next example tells us we cannot. The inductive proof uses a statement that is not true for 0, and for which we must choose a larger basis, namely 1.