The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+20 votes
1.1k 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 (68.8k points)
edited by | 1.1k views

3 Answers

+16 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 (332k points)
edited 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.
+8 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 Veteran (30.5k points)
+3 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 Veteran (13k 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

32,443 questions
39,189 answers
108,813 comments
36,563 users