Question

Let $x_n$ denote the number of binary strings of length n that contain no concecutives 0s.
The value of $x_5$ is

• A. 5
• B. 7
• C. 8
• D. 13

Answer 1

The correct option is D 13

$x_1$ = 2
$x_2$ = 3
$\Rightarrow$ $x_3$ = $x_1$ + $x_2$ = 2 + 3 = 5
$\Rightarrow$ $x_4$ = $x_2$ + $x_3$ = 3 + 5 = 8
$\Rightarrow$ $x_5$ = $x_3$ + $x_4$ = 5 + 8 = 13
So option (d) is correct.