Please take note an should be a subscript n

Please take note an should be a subscript n

Let an be the number of bit strings of length n containing two consecutive 0s. These an strings consist of:

the strings starting with 1 --- the number is an-1

the strings starting with 01 --the number is an-2

the strings starting with 00 --the number is 3n−2

Therefore, the recurrence relation is:

an = an−1 + an−2 + 3n−2 , for n ≥ 3

Initial conditions: a1 = 0, a2 =1

a3 = a2 + a1 + 31 = 1 + 0 + 3 = 4

a4 = a3 + a2 + 32 = 4 + 1 + 9 = 14