1

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 :(.

user1176409
  • 1
Will
  • 11
  • 1
    To find a recurrence relation, you need to relate the number of such strings of length $k+1$ to the number of such strings of length $k$. (For example, "each ternary string of length $k+1$ with at least one zero can be got by either appending any digit to a ternary string of length $k$ that already has at least one zero, or by appending $0$ to a ternary string of length $k$ that has no zeroes.".) – ShreevatsaR Mar 14 '14 at 02:22
  • Good luck with your class by the way, just keep at it and don't despair. :-) Things will become clear if you spend enough time thinking carefully about the stuff. – ShreevatsaR Mar 14 '14 at 02:23
  • Am I approaching the problem correctly? – Will Mar 14 '14 at 02:39
  • What you've done so far is correct, but it doesn't go any distance towards finding a recurrence relation. Finding a recurrence relation means writing down an expression for the answer for $k+1$ in terms of the answer for $k$ (and possibly smaller numbers). My first comment above almost gives away the answer, please read it carefully and think about it. Or, ignore the comment and try it yourself from scratch. – ShreevatsaR Mar 14 '14 at 08:33

1 Answers1

0

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$)
vonbrand
  • 27,812