The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+22 votes
1.4k 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}$
asked in Algorithms by Veteran (59.5k points)
edited by | 1.4k views
+1
0

3 Answers

+19 votes
Best answer
$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 and for all strings ending in $0$, we get a new string. So, the new set of strings for $n+1$, will have exactly $n$ strings ending in $1$)

$x_{5}= 8+5 = 13$
answered by Veteran (357k points)
edited by
0
Sir, can you elaborate bit more?
+3
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.
+12 votes

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

 

answered by Boss (30.8k points)
+5 votes

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

answered by Boss (15k points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

39,437 questions
46,622 answers
139,351 comments
57,004 users