Find a recurrence relation for the number of ternary strings of length n that contain at least one 0. Ternary string only contains 0s, 1s, and 2s.

Question

Problem: Find a recurrence relation for the number of ternary strings of length n that contain at least one 0.

Ternary string only contains 0s, 1s, and 2s.

Approach: Assuming that the length n is equal or bigger than 3 (n >= 3) then:

• When n = 1, there is 1 possibility to obtain a string with at least a zero
• When n = 2, there is 5 possibilities to obtain a string with at
  least a zero
• When n = 3, there is 19 possibilities to obtain a string with at least a zero (Not sure if correct)

And from here I am completely lost on how to start forming the recurrence. Any help/hints? I been having a terrible semester with this class :(.

Answer 1

Two ways of solving this:

• Call $a_n$ the number of strings with at least one zero and length $n$, similarly $b_n$ those which have no zeros. Then you see that: \begin{align} a_{n + 1} &= 3 a_n + b_n \quad \text{add $0$ to a $b_n$ or anything to an $a_n$} \\ b_{n + 1} &= 2 b_n \hspace{3.4em} \text{add $1$ or $2$ to a $b_n$} \end{align} Also, $a_0 = 0$ and $b_0 = 1$. This you can massage into a single recurrence by considering $a_{n + 2}$
• This is just the total number of strings of length $n$ ($3^n$) less the ones which don't include $0$ ($2^n$)