The Gateway to Computer Science Excellence
+36 votes
3.7k views

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}$
in Algorithms by Boss (30.7k points)
edited by | 3.7k views

3 Answers

+60 votes
Best answer

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

A is choice.

by Veteran (430k points)
edited by
0

Hi Arjun,

Please clarify for the recurrence relation an' = an-1' + an-2'
lets take some example :
Consider length of string is 3 and string be 001
then 
001 = 00 + 1 

and 2^n - an  Will be those numbers which are having consecutive 1.

Is it so ?

Thanks

0
I have added more explanation. an is the count of the number of bit strings not containing two consecutive 1's.
+1
I got it very well. Thanks Man !
0
please explain line no-3 to 8
+4

It's strange. This question was asked in GATE in 2015, while it was already asked by someone in math.stackexchange in 2013. Here: https://math.stackexchange.com/questions/603341/recurrence-relation-for-number-of-bit-strings-of-length-n-that-contain-two-conse

0
Wow ... Clever approach ...
+1
Yes ,you are right. It's Strange.

He's got time stone.
+33 votes

 

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

answer = option A

by Boss (30.8k points)
+14 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.
by (383 points)
Answer:

Related questions

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
50,741 questions
57,252 answers
198,061 comments
104,697 users