Question

Consider strings that contain only the characters A, B, C, D and E.

1- Find a recurrence relation for the number of such strings that contain three consecutive Bs.

2- What are the initial conditions?

Answer 1

Let T(n) denotes number of strings that contain 3 consecutive B's.

If a n bit string starts with a,c,d,e then,problem dissolves to finding T(n-1)

similarly if n bit string starts with ba,bc,bd,be then, problem dissolves to finding T(n-2).

if n bit string starts with  bba,bbc,bbd,bbe then, problem dissolves to finding T(n-3).

if n bit string starts with bbb,then each of remaining n-3 bits can have 5 choices(a,b,c,d,e).there fore,number of such strings=

on total recurrence equation is

where n>=3

base conditions are

T(0)=0

T(1)=0

T(2)=0

T(3)=1

T(4)=9