4,974 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?

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}$

### Subscribe to GO Classes for GATE CSE 2022

$0 \ 1 -2$
$01 \ 10 \ 11 -3$
$010 \ 011 \ 101 \ 110 \ 111 -5$
$0101 \ 0110 \ 0111 \ 1010 \ 1011 \ 1101 \ 1110 \ 1111 -8$

So, $x_n = x_{n-1} + x_{n-2}$ (For all the strings ending in $1$, we get two new strings ending in either $0$ or $1$ and for all strings ending in $0$, we get a new string ending in $1$. So, the new set of strings for $x_{n}$, will have exactly $x_{n-1}$ strings ending in $1$ and $x_{n-2}$ strings ending in $0)$

$x_{5}= 8+5 = 13$

Correct Answer: $D$
by

Sir, can you elaborate bit more?
Consider set of strings of length n. There will be strings ending in 0's as well as 1's. For, every string ending in 0, we append 1 and we get a string of length n+1, without 00. For every string ending in 1, we can append either 0 or 1 and thus we get two possible strings of length n+1 without a 00.
Sir, why can't we take a0=0? please explain
@arjun sir

"So, the new set of strings for n+1, will have exactly n strings ending in 11"

how did we get this ? i understood till the point where it is said that we will 2 new strings when string ends in 1. what does "the new set of strings for n + 1" mean?
Can you see now?

Yes sir. Now the example is a lot clearer. Thanks.

This problem contains both properties , Optimal Substructure and the Overlapping Subproblems. Correct me if I'm wrong.

$x_n$ denote the no. of the binary string of length n that contains no consecutive 0's.

Either the string can end with 0 or 1.

If the string ends with 1 then we will find $x_{n-1}$. (The no. of the binary string of length n - 1 that contains no consecutive 0's.).

$\underbrace{ x_{n - 1} }$  1

If the string ends with 0, then second last string must be 1. (Think !). Now, we will find $x_{n-2}$, the no. of the binary string of length n - 2 that contains no consecutive 0's.

$\underbrace{ x_{n-2}}$ 10.

Recurrence relation,

$x_1$ = 2

$x_2$ = 3

$x_n$ =  $x_{n-1}$ + $x_{n-2}$  | n > 2.

$n=1$
0
1

$n=2$
00 = fails
01
10
11

$n=3$
so here we will make possible combinations with the above three valid strings of previous case(n=2) only; and to get new strings of length 3, we can put either zero or 1 on the front of valid strings of the previous case, so we get:
0 01 = fails
0 10
0 11
1 01
1 10
1 11
here in this case we get 5 strings; pattern which option D says resembles here.
answer for Q.78 = option D

answer for Q.79 = $x_5 = x_4 + x_3 = 8 + 5 = 13$ but no option matches so we select the closest which is option D
its wrong to do like this but.. we are out of choices here.

This can also be a solution.

by
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}$
by
x1 = 0, 1  [Total = 1 (since 0 is not considered)]

x2 = 10,11 [Total = 2]

x3 = 100,101,110,111 [Total = 3]

x4 = 1000,1001,1010,1011,1100,1101,1110,1111 [Total = 5]

Applying for x4 we get that option D satisfies it -

x4 = x3+x2

= 3+2 = 5

[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.

by