Question

Let $a_n$ represent the number of bit strings o length n containing two consecutive 1s. Whats the recurrence ralation 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}$

Answer 1

The correct option is A $a_{n-2}+a_{n-1}+2^{n-2}$

$a_1=0$ [no strings of length 1 contain two consecutive 1's]

$a_2=1[\therefore strings=11]$
$a_3=3[\therefore$ strings are : 011, 110,111]
$a_4=8[\therefore$ strings are : 0011, 0110, 0111, 1011, 1100, 1101, 1110, 1111]

Option (a):
$a_n=a_{n-2}+a_{n-1}+2^{n-2}$
$\Rightarrow a_4=a_{4-2}+a_{4-1}+2^{4-2}$
$=a_2=a_3+2^2$
= 1+3+4 = 8 which is True.

Option (b):
$a_n=a_{n-2}+2a_{n-1}+2^{n-2}$
$\Rightarrow a_4=a_2+2a_3+2^2$
= 1+2x3+4=11 which is false.

Option (c) :

$a_n=2a_{n-2}+a_{n-1}+2^{n-2}$
$\Rightarrow a_4=2a_2+a_3+2^2$
= 2x1+3+4 = 9 which is false.

Option (d):

$a_n=2a_{n-2}+2a_{n-1}+2^{n-2}$
$\Rightarrow a_4=2a_2+2a_3+2^2$
= 2x1+2x3+4 = 12 which False.
$\therefore Option\left(a\right):a_n=a_{n-2}+a_{n-1}+2^{n-2}$ is correct.



​​​​​​​