Auto Generated Question

Back

1 . For any integer

n \geq 1

, let

B_{n}

be the number of bitstrings of length

n

that do not contain the substring 11 and do not contain the substring 101. Which of the following is true for any

n \geq 4

(a)

B_{n} = B_{n - 1} + B_{n - 3}

(b)

B_{n} = B_{n - 1} + B_{n - 2}

(c)

B_{n} = B_{n - 2} + B_{n - 4}

(d)

B_{n} = B_{n - 2} + B_{n - 3}