Q78

MCQ2 marks, −0.5

Let $x_n$ denote the number of binary strings of length $n$ that contain no consecutive $0$ s. Which of the following recurrences does $x_n$ satisfy?

(A)

$x_n = 2x_{n-1}$

(B)

$x_n = x_{\lfloor n/2 \rfloor} + 1$

(C)

$x_n = x_{\lfloor n/2 \rfloor} + n$

(D)

$x_n = x_{n-1} + x_{n-2}$

Loading…