Question

A) Find a recurrence relation for the number of bit strings of length n that contain a pair of consecutive 0s.

Answer 1

Answer:

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

B) $a_{0} = a_{1} = 0$

C)   for n = 2

  $a_{2}$ = 1

for n = 3

 $a_{3}$ = 3

for n = 4

$a_{4}$ = 8

for n = 5

$a_{5}$ = 19

Step-by-step explanation:

A) A recurrence relation for the number of bit strings of length n that contain a  pair of consecutive Os can be represented below

if a string (n ) ends with 00 for n-2 positions there are a pair of  consecutive Os therefore there will be : $2^{n-2}$ strings

therefore for n ≥ 2

The recurrence relation for the number of bit strings of length 'n' that contains consecutive Os

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

b ) The initial conditions

The initial conditions are : $a_{0} = a_{1} = 0$

C) The number of bit strings of length seven containing two consecutive 0s

here we apply the re occurrence relation and the initial conditions

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

for n = 2

  $a_{2}$ = 1

for n = 3

 $a_{3}$ = 3

for n = 4

$a_{4}$ = 8

for n = 5

$a_{5}$ = 19