For any integer $n ≥ 3$, let $B_n$ be the number of bitstrings of length $n$ in which the first three bits are not all equal. Which of the following is true?
(a) $B_n = 2 \cdot 2^{n-3}$
(b) $B_n = 6 \cdot 2^{n-3}$
(c) $B_n = 2^{n} - 2$
(d) $B_n = 2^{n} - 6$
I can see that it is (b) because the number of ways for bitstrings of length $3$ to not have all equal bits is the same as $2^{n} - 2$ which removes the bitstrings $111$ and $000$, meaning there are $6$ possible ways for bitstrings whose first $3$ bits are not equal. Now, we choose the remaining $n-3$ by doing $2^{n-3}$ which comes out to $B_n = 6 \cdot 2^{n-3}$.
My Question:
What if I wanted to take the complement and calculate it that way? What am I doing wrong? This is my answer:
There are $2$ ways that a bitstring can start with $3$ equal bits:
- $111$ followed by $n-3$ arbitrary bits, and
- $000$ followed by $n-3$ arbitrary bits.
There are two ways to do this, so:
$2 \cdot 2^{n-3} = 2^{n-2}$
Subtract this from all bitstrings of length $n$ to get all bitstrings that do not start with $111$ or $000$:
$2^{n} - 2 \cdot 2^{n-3}$
$= 2^{n} - 2^{n-2}$
$\ldots$
$= 3 \cdot 2^{n-2}$
The answer I got was the same, however it was over simplified:
$3 \cdot 2^{n-2} = 3 \cdot 2 \cdot 2^{n-2} = 6 \cdot 2^{n-3}$
Thank you @NFTaussig.