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

edited | 3.7k views

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

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

answer = option A

by Boss (30.8k points)
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)

1