Question

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

• A. $x_n$ = 2$x_{n-1}$
• B. $x_n$ = $x_{\left[n/2\right]}$ + 1
• C. $x_n$ = $x_{\left[n/2\right]}$ + n
• D. $x_n$ = $x_{n-1}$ + $x_{n-2}$

Answer 1

The correct option is D $x_n$ = $x_{n-1}$ + $x_{n-2}$

The represents those strings with no consercutive 0's
Let, n = 1

$x_1$ = 2
Let, n = 2

$x_2$ = 3
Let, n =3

$x_3$ = 5
Now, substituting n = 3 in all of the answers only choice (d) $x_n$ = $x_{n-1}$ + $x_{n-2}$ satisfies the number obtained from the tree counting.