GATE CSE 2015 | Set 1 | Question: 49

Question

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

• A. $a_{n - 2} + a_{n - 1} + 2^{n - 2}$
• B. $a_{n - 2} + 2a_{n - 1} + 2^{n - 2}$
• C. $2a_{n - 2} + a_{n - 1} + 2^{n - 2}$
• D. $2a_{n - 2} + 2a_{n - 1} + 2^{n - 2}$

Comments

Notice the variation https://gateoverflow.in/497/gate2008-78

https://gateoverflow.in/39636/gate2016-1-2

---

$\color{red}{\text{Detailed Video Solution of this GATE question}}$(Click Below):

Detailed Video Solution

$\color{red}{\text{Complete Recurrence Relation Playlist}}$(Click Below):

Complete Recurrence Relations Playlist 

---

if the last bit is 1 then aN = a(N-1)

or

if the bits are 10, then  aN = a(N-2)

or

if the bits are 00, then aN = 2^(n-2)

so, aN =  a(N-1) + a(N-2) + 2^(n-2)

---

a2 = for length two string => one possibility =>  11
a3 = for length three  =>  three possibility => 110, 011, 111
a4 = for length four  =>  eight possibility  => 0011 , 0110, 1100, 0111, 1110, 1011, 1101, 1111
put n = 4

Answer 1

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

Comments

Wow ... Clever approach ...

---

Rishabh Gupta 2,

Yes, you are right. It's Strange.

He's got time stone.

---

can someone elaborate from 2^nd last step

Answer 2

 

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

answer = option A

Comments

Nice explanation ..

---

nice approach

Answer 3

we can break this problem into different cases:

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

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.

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 cases 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 variants of this problem,
For 2 consecutive 0s, everything remains same; just replace 0 with 1, and 1 with 0.

For no consecutive 0s ( or for no consecutive 1s, after doing same replacement here as well)
It goes as follows: (explaining for no consecutive 0’s)

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

For adding 0, we have to be careful. Let us move to the last two bits.

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 the previous case(adding 1 at last bit)
We are left with only one possible way: 10. This case gives $a_{n-2}$
We are done, as we have seen all the possible cases.

Therefore, for no consecutive 0’s

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

Comments

Best answer!

---

@Nikhil_dhama

Very nice solution

Answer 4

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 5

You can just do this question using option elimination but let's understand what's the logic behind it

We want to find recurrence for number of strings of length n having two consecutive 1

Let number of strings of length n having two consecutive 1 be 'an'

Now we will have cases

A) what if string ends with 0

In this case we need to find number of strings of length n-1 having two consecutive 1

So it will 'an-1'

B) what if strings ends with 1

In this case you will have two cases

1) either string ends with 01 or 11

If the string is ending with 01 then we need to find number of strings of length n-2 having two consecutive 1

ie it will be 'an-2'

But if string ends with 11 we already have two consecutive 11 now we just need to find number of strings of length n-2.

Each position will have 2 choices which is total 2^n-2

Finally recurrence is

an= an-1+ an-2+ 2^n-2