A)find a recurrence relation for the number of ternary strings of length n that do not contain two consecutive 0s. b) what are the initial conditions? c) how many ternary strings of length six do not contain two consecutive 0s?

Denote by the number of ternary strings of length n

Step-by-step explanation:

a) Let be a ternary string of length n. If , then S can be decomposed as where is a ternary string of length n-1 with no consecutive zeros. In this case, there are choices for therefore the number of strings S which last is digit 1 is . Similarly, the number of ternary strings S with is . We conclude that the number of strings S whose last digit is 1 or 2 is

Now, if , then or because S does not have consecutive zeroes. Then or where is a ternary string of length n-2 with no consecutive zeros. Thus, the number of such strings S is equal to the number of strings P whose last digit is 1 or 2 is . Applying the same reasoning from before, this number is equal to  .

Any string S has its last digit equal to 0,1 or 2 then by the sum rule, .

b) 0,1,2 are the strings of length 1 with no consecutive zeroes. Then . The corresponding strings of length 2 are 01,02,10,11,12,20,21,22, thus .

c) This follows froma applying the recurrence relation repeatdly. .

898.1666667

step-by-step explanation:

5389/6 = 898.1666667