For n ≥ 1, let bₙ be the number of binary strings of length ...

Prompt

For n ≥ 1, let bₙ be the number of binary strings of length n that contain no two consecutive 1s and no three consecutive 0s. (a) Find b₁, b₂, b₃ by listing. Then find and justify a recurrence for bₙ when n ≥ 4. (b) Using (a), prove that bₙ = bₙ₋₁ + bₙ₋₅ for all n ≥ 6. (c) Compute b₁₀. (d) How many of the strings counted by b₁₀ contain exactly four 1s? Justify your answer.