# GATE2008-78

3.2k views

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

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
1
0

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

edited
1
Sir, can you elaborate bit more?
8
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.
0
Sir, why can't we take a0=0? please explain
0
@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?
0
Can you see now?
0

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

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

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

This can also be a solution.

## Related questions

1
1.6k views
Let $x_n$ denote the number of binary strings of length $n$ that contain no consecutive 0s. The value of $x_5$ is $5$ $7$ $8$ $16$
Consider the following C program that attempts to locate an element $x$ in an array $Y[ \ ]$ using binary search. The program is erroneous. f (int Y[10] , int x) { int u, j, k; i= 0; j = 9; do { k = (i+ j) / 2; if( Y[k] < x) i = k;else j = k; } while (Y[k] != x) && (i < j)) ; if( ... $(Y[k] < x) i = k$; else $j = k$; Change line 7 to: } while $((Y[k] == x) \&\& (i < j))$ ;
Consider the following C functions: int f1 (int n) { if(n == 0 || n == 1) return n; else return (2 * f1(n-1) + 3 * f1(n-2)); } int f2(int n) { int i; int X[N], Y[N], Z[N]; X[0] = Y[0] = Z[0] = 0; X[1] = 1; Y[1] = 2; Z[1] = 3; for(i = 2; i <= n; i++){ ... X[i]; Z[i] = 3 * X[i]; } return X[n]; } $f1(8)$ and $f2(8)$ return the values $1661$ and $1640$ $59$ and $59$ $1640$ and $1640$ $1640$ and $1661$
The subset-sum problem is defined as follows. Given a set of $n$ positive integers, $S = \{ a_1, a_2, a_3, \dots , a_n \}$, and positive integer $W$, is there a subset of $S$ whose elements sum to $W$? A dynamic program for solving this problem uses a $\text{2-dimensional}$ Boolean array, $X$ ... , implies that there is a subset whose elements sum to $W$? $X[1, W]$ $X[n, 0]$ $X[n, W]$ $X[n-1, n]$