- #1
Mr Davis 97
- 1,462
- 44
Homework Statement
Find a recurrence relation for the number of ternary strings of length n that contain two consecutive 0s.
Homework Equations
The Attempt at a Solution
Let ##a_n## count the number of ternary stings of length n that contain two consecutive 0s. Then, we can split the total number into mutually exclusive cases. If we start with 1 or 2, then we have ##a_{n-1}## in both cases. If we start with 01 or 02, then we have ##a_{n-2}## in both cases. If we start with 00, then we have ##3^{n-2}## possibilities for the other strings, since we already have two consecutive zeroes. Thus ##a_n = 2a_{n-1} + 2a_{n-2} + 3^{n-2}##.
However, apparently the solution is ##a_n = 2a_{n-1} + 2a_{n-2} + 2^{n-2}##. Is this correct or is mine correct?