edited by
5,193 views
24 votes
24 votes

Let $x_n$ denote the number of binary strings of length $n$ that contain no consecutive $0$s.

The value of $x_5$ is 

  1. $5$
  2. $7$
  3. $8$
  4. $16$
edited by

6 Answers

Best answer
9 votes
9 votes

We can write the recurrence for the number of binary strings of length $n$ without consecutive $0$s as

  • $T(n) = T(n-1) + T(n-2);\qquad n>2$
  • $T(1) = 2;T(2) = 3$

The reason for this recurrence can be seen as follows:

  • A string of length $n$ without $“00”$ can be formed by adding
    • a $``1”$ to any string without $``00”$ of length $n-1\quad \to T(n-1)$
    • a $``0”$ to any string ending in $``1”$ and without $``00”$ of length $n-1\quad \to T(n-2)$
    • These two cases are mutually exclusive (no common strings) and exhaustive (no strings outside these two cases). So, we can just add the two cases to get $T(n)$  


$T(1) =2\quad-\quad \{0,1\}$
$T(2) =3\quad-\quad \{01,10,11\}$
$T(3) = T(1) + T(2) = 2+3 = 5$
$T(4) = T(3) + T(2) = 5 + 3 = 8$
$T(5) = T(4) +T(3) = 8 + 5 = 13$

Hence, the answer is 13.

No option matches.

edited by
22 votes
22 votes
Here X1 =0,1(2)

X2=01,10,11(total 3)

X3=010,011,101,110,111(total 5)

Here X3=X2+x1

X4=3+5=8

X5=5+8=13

No option matching here.
6 votes
6 votes
$\mathbf{\underline{Answer:}\Rightarrow}$ No option matches (Answer $\mathbf{=13}$)

$\mathbf{\underline{Explanation:}\Rightarrow}$

Though everyone has already given the correct answer but let me try an easier explanation.

You can do it by hit and trial method.

The smallest string you can think of in the first attempt is

Let's say $\mathbf{x_1}$, then it should contain either $\mathbf 0 \;  \text{or}\; \mathbf 1$.

So, for $\mathbf{x_1}\; \textbf{Answer} = \mathbf 2$

For $\mathbf{x_2}$, it may contain, $11, 10 \; \text{or}\; 01  \rightarrow = 3$

Similarly, for $\mathbf{x_3}$, it may contain, $111, 110, 101, 011, 010 \rightarrow = 5$

Now, you can see that it is forming a series like $2, 3, 5, ...$, and so on.

Recall, this popular series. It's nothing but the Fibonacci series.

So, here's your answer.

since, $\mathbf{f(n) = f(n-1) + f(n-2)}$, (By Fibonacci Series)

So, $\mathbf{f(5) = f(4) + f(3), ...............(1)}$

$\mathbf{f(4) = f(3) + f(2) = 5 + 3...........(2)}$

Putting this value of equation $\mathbf{(2)}$ in equation $\mathbf{(1)}$, we get:

$\mathbf{f(5) = 8 + 5}$

$\therefore \; \textbf{Answer} = 13$
edited by
Answer:

Related questions

42 votes
42 votes
10 answers
1
Kathleen asked Sep 12, 2014
8,391 views
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?$x_n = 2x_{n-1}$$x_n = ...