edited by
10,274 views
58 votes
58 votes

Let a$_{n}$ represent the number of bit strings of length n containing two consecutive $1$s. What is the recurrence relation for $a_{n}$?

  1. $a_{n - 2} + a_{n - 1} + 2^{n - 2}$
  2. $a_{n - 2} + 2a_{n - 1} + 2^{n - 2}$
  3. $2a_{n - 2} + a_{n - 1} + 2^{n - 2}$
  4. $2a_{n - 2} + 2a_{n - 1} + 2^{n - 2}$
edited by

4 Answers

Best answer
92 votes
92 votes

Counting the number of bit strings NOT containing two consecutive $1$'s. $($It is easy to derive a recurrence relation for the NOT case as shown below$)$

$0 \quad 1$
$00 \quad 01 \quad 10 - 3$ $($append both $0$ and $1$ to any string ending in $0$, and append $0$ to any string ending in $1$$)$
$000 \quad 001 \quad 010 \quad 100 \quad 101 - 5$ $($all strings ending in $0$ give two strings and those ending in $1$ give $1$ string$)$
$0000 \quad 0001 \quad 0010 \quad 0100 \quad 0101 \quad 1000 \quad 1001 \quad 1010 - 8$
$\vdots$

$a_n' = a_{n-1}' + a_{n-2}' $ $($where $a_n$ denote the number of bit strings of length $n$ containing two consecutive $1$s$)$

$2^n - a_n = (2^{n-1}  - a_{n-1}) + (2^{n-2} - a_{n-2})$

$a_n= 2^{n-2}(4 - 2 - 1) + a_{n-1} +a_{n-2}$

$a_n= a_{n-1} + a_{n-2} + 2^{n-2}$

Correct Option: A

edited by
51 votes
51 votes

 

apply value putting and try to satisfy options using these values.
only option A holds good.

answer = option A

19 votes
19 votes

we can break this problem into different cases:

Now first assume we already build the string of length n-1 and then,

  1. we want to add 0 at the end of it (we are concatenating at right end),  we know adding a zero can’t increase the number of string with consecutive ones.  
    • so $a_{n-1}$ is the number of strings of length n-1 with 2 consecutive one, we then add a 0, this number remains the same.
    •  
  2. we want to add a 1 at the end, here we need to be little careful about whether last element of string of length n-1 is 1 or 0,  so we have to analyze last 2 bits instead of 1,
    • for 2 bits, cases for 00 and 10 are covered in case 1 (adding 0 at the end).
    • we left with two case 01 and 11
    • adding 01 at the end of a string of length can’t add any extra consecutive 1’s, so this gives $a_{n-2}$ possible strings
    • lastly we are adding 11, which is itself a pair of consecutive ones, so irrespective of what we have in those n-2 bits, adding 11 make all of them a string with two consecutive 1’s, So there are $2^{n-2}$ possible string of length n-2, and we are adding 11 at the end, so this case gives $2^{n-2}$ strings with two consecutive 1’s

Adding all together, $a_{n}$ will be:

  • $a_{n-1}$ (adding 0 at the end.)
  • $a_{n-2}$ (adding 01 at the end)
  • $2^{n-2}$ (adding 11 at the end)

$a_{n} = a_{n-1} + a_{n-2} + 2^{n-2}$

 

(All these cases are disjoint, string from case 1(adding 0)  and case 2(adding 01) are disjoint because of last bit is different, similarly case1(adding 0) and case 2(adding 11) are different, case 2 and 3 are disjoint by their second last bit)


A similar kind of analysis can be done for all variant of this problem,

For 2 consecutive 0’s everything remains same, just replace 0 with 1, and 1 with 0.

For no consecutive 0’s ( or for no consecutive 1’s, after doing same replacement here as well)

it goes as follows: (explaining for no consecutive 0’s)

we get string of length n-1 by recursion, we can add 1 at the end with worrying about anything, because adding 1 can never generate consecutive ones, so we get $a_{n-1}$ for string of length n-1,

for adding 0 we have to be careful, lets move to last two bit,

last two bits can be 10, 01,11 ( it can’t be 00, because that is generating consecutive 0’s)

01, 11 both are covered in previous case(adding 1 at last bit)

we left with only one possible way, 10.. this case gives $a_{n-2}$

we are done as we have exploited all the possible cases,

therefore for no consecutive 0’s

$a_{n} = a_{n-1} + a_{n-2}$

16 votes
16 votes
For strings with consecutive 1s,
 

a0=0

a1=0

a2 =11 (total 1) ,

a3= 011,111,110  (3),

a4= 0011,1011,0110,0111,1111,1110,1100,1101 (total 8)...by backtracking,option a and c satisfy a3 and only a satisfies a4..so a is the answer.
Answer:

Related questions