edited by
8,381 views
42 votes
42 votes

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?

  1. $x_n = 2x_{n-1}$
  2. $x_n = x_{\lfloor n/2 \rfloor} + 1$
  3. $x_n = x_{\lfloor n/2 \rfloor} + n$
  4. $x_n = x_{n-1} + x_{n-2}$
edited by

10 Answers

1 votes
1 votes
I think that some of the previous answers have touched upon this point, but to just give a complete explaination...

{Here $a_{n}$ represents every n-bit string that is counted by $x_{n}$}

We start thinking how can we construct $a_n$ from $a_{n-1}$, such that there are no adjacent zeroes..

When using $a_{n-1}$, we know that the $zero^{th} place$ digit can be $0$ or $1$.

And to construct $a_{n}$, we must choose from among { $0a_{n-1}$ , $1a_{n-1}$ }, where exactly those strings where $a_{n-1}$ has $0$ at the $zero^{th} place$ and from the group $0a_{n-1}$ have a repeating zero.

So we can write $x_{n} = x_{n-1} + (No. \ of \ strings \ with\ '01'\ fixed \ at \ start) $

Since, only $n-2$ bits are changing,it's as good as counting $x_{n-2}$ bit strings

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

[The question has been answered very nicely by seniors already, so here I am just adding the common doubt people have been asking.]

If we append ‘1’ to all the (n-1)length strings and ‘10’ to all the strings of (n-2)length then we will be able to cover all cases. HOW?

Now you might think that we can also append ‘11’ to all (n-2) length strings. Yes, but that case will be covered by appending ‘1’ to all (n-1)length strings.

1st QUESTION: Why are we just appending ‘1’ to all the (n-1)length strings?

Ans: Because some (n-1) length string might end with 0 and we don’t want to have consecutive 0s.

2nd QUESTION: So when will we cover cases of (n-1)length string, where we can append 0 without conflict?

Ans: That will be taken care when we append ‘10’ to all the (n-2)length strings.

edited by
1 votes
1 votes
        1

1st case:Suppose we have this like above n length string which ends with 1 then for remaining n-1 places we have to confirm that there is no consecutive 0’s so for that → $x_{n-1}$

      1 0

2nd case:Suppose we have this like above n length string which ends with 0 so before that 1 must be there as mentioned in question we can’t have consecutive 0’s then for remaining n-2 places we have to confirm that there is no consecutive 0’s so for that → $x_{n-2}$

So this both cases sum up to $x_{n-1}$ + $x_{n-2}$

Answer : D

 

Answer:

Related questions

24 votes
24 votes
6 answers
1
go_editor asked Apr 23, 2016
5,189 views
Let $x_n$ denote the number of binary strings of length $n$ that contain no consecutive $0$s.The value of $x_5$ is $5$$7$$8$$16$