For any integer $n ≥ 1$, let $B_n$ be the number of bitstrings of length $n$ that do not contain the substring $10$. Which of the following is true for any $n ≥ 4$?
Answer: $B_n = n + 1$
I can see that the pattern goes like:
$0 \ldots 0$
$0 \ldots 01$
$0 \ldots 011$
$0 \ldots 0111$
$0 \ldots 01111$
$\vdots$
$1 \ldots 1$
How can I put this in a formal explanation? Initially I thought I needed to set up a recurrence relation, but seeing the answer then that doesnt need to be done. I can't quite grasp how I would write out a short and nice solution to this.
Well, you've got the pattern right, so the only question is how to explain it. The point is that once you get a $1$ bit, all the remaining bits must also be $1$, so the pattern is a string (perhaps empty) of $0$ bits, followed by a string (perhaps empty) of $1$ bits. The length of the string of $0$ bits is an integer from $0$ to $n$, so there are $n+1$ possibilities.