The number of bit strings of length eight that will either start with a 1 bit…

Concept. For two finite sets A and B, adding |A| and |B| counts every element of A ∩ B twice, so the inclusion–exclusion principle gives |A ∪ B| = |A| + |B| − |A ∩ B|. By the product rule, a binary string of length n with k of its positions pinned to specific bits leaves n − k free positions, so exactly 2n−k such strings exist.

Application. Take A as the length-eight bit strings whose first bit is 1, and B as the length-eight bit strings whose last two bits are 00.

1. In A the first position is pinned and the other seven are free, so |A| = 27 = 128.

2. In B the last two positions are pinned and the other six are free, so |B| = 26 = 64.

3. In A ∩ B the first position and the last two positions are pinned together, leaving five free, so |A ∩ B| = 25 = 32.

4. The phrase either … or … asks for the union of the two families, so |A ∪ B| = 128 + 64 − 32 = 160.

Cross-check. Split the same union into three disjoint blocks and add their sizes.

• First bit 1 and last two bits not 00: 27 − 25 = 96.

• First bit 0 and last two bits 00: 26 − 25 = 32.

• First bit 1 and last two bits 00: 25 = 32.

These give 96 + 32 + 32 = 160. Counting the complement agrees: of the 28 = 256 strings of length eight, exactly 27 − 25 = 96 begin with 0 and do not end in 00, and 256 − 96 = 160.

Result. 160 bit strings of length eight begin with a 1 bit or end with 00.