Find and solve a recurrence equation for the number “gn” of ternary strings of length n that do not contain $102$ as a substring.

Question

Find and solve a recurrence equation for the number gn of ternary strings of length n that do not contain $102$ as a substring.

I am having some trouble finding the recurrence relation for this question. My thinking is that you can set this problem into cases. If the last digit of the ternary string is $0,1$,or $2$, then there is $3g(n-1)$ possible cases of length $n-1$. Then, continue to do the same for the next digits.

Any help would be appreciated. Thanks!

Answer 1

Consider a ‘good’ string of length $n$. If it does not end in $10$, you can append any of the three digits to make a good string of length $n+1$. If it does end in $10$, however, you can only append a $0$ or a $1$. Thus, if $a(n)$ is the number of good strings of length $n$ that end in $10$, we must have

$$g(n+1)=3\big(g(n)-a(n)\big)+2a(n)=3g(n)-a(n)\;.$$

Of course we want to get rid of $a(n)$ in favor of some combination of values of $g$. A good string of length $n$ that ends in $10$ is simply a good string of length $n-2$ with $10$ appended, and any good string of length $n-2$ will work here: appending $10$ to a good string always creates another good string. Thus, $a(n)=\ldots\;$?

Answer 2

I am learning this right now...

I find it helpful to think of it this way:

building from the end of the string,

___1 = g(n-1) combinations; splits into:

• ___11 = g(n-2)
• ___01 = g(n-2)
• ___21 = g(n-2)

since they are all legal strings, we keep all of them, so you add g(n-1) to your recursion.

---

___0 = g(n-1) combinations; splits into:

• ___00 = g(n-2)
• ___10 = g(n-2)
• ___20 = g(n-2), All legal: add g(n-1) to recursion

  ---

___2 = g(n-1) combinations; splits into:

• ___02 = g(n-2) combinations; splits into:

     ____002 = g(n-3)
     ____102 = g(n-3) NOT LEGAL
     ____202 = g(n-3)
  

• ___12 = g(n-2)

• ___22 = g(n-2)

Summing everything together, you note that 02 contributes: g(n-2) - g(n-3), and, having already established, by virtue of the ternary property, that g(n-1) = 3g(n-2), you get that __2's contribution is g(n-1) - g(n-3).

Summing everything together, you have:

$$ 3g(n-1) - g(n-3) = g(n) $$

And that just makes sense to me, because this is a tree we are talking about...and this explanation unfolds like a breadth first search reinterpreted as a recursion. Super intuitive.