Prove that the recurrence is true

Question

I am working on an assignment question, and am having trouble moving ahead. The question is as follows:

Let the total number of bit strings with three consecutive zeros be $t_n$. Prove for $n \ge 4$ that $t_n= t_{n-1} + t_{n-2} + t_{n-3} + 2^{n-3}$

So, I started to check if the base case is true with n=4
$t_4 = t_3 + t_2 + t_1 + 2^1 = 1 + 0 + 0 + 2 = 3$

But isn't the total number of combinations for n =4 only 2? 1000 or 0001

I might just be going about this the wrong way. Any guidance would be appreciated.

Answer 1

Base case is fine if you include the option of more than 3 consecutive zeros:

$$ t4: 1000, 0000, 0001 $$

Breaking the problem down, you can consider the first bit as either 1 or 0. For one, there are no extra results and you get t3. For 0, you get a bonus set of cases where the first 3 are zero, which occurs 2^(n-3) times. Repeating the process for the second and third digit - minus the already counted cases in 2^(n-3) - and you get the rest of the argument you were requested to prove.