# Recurrence Relations with ternary strings

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!

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.

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\;$?

• You mean $10$ not $01$ in the second paragraph. Jun 27, 2015 at 21:23
• @pre-kidney: I do indeed; thanks. Jun 27, 2015 at 21:24
• @BrianM.Scott I tend to find recurrence relation problems difficult to translate into a recurrence relation, do you have a technique or a tip to tackle these questions? I would really appreciate some sort of approach to these types of questions. Jun 27, 2015 at 22:03
• @newtothis1995: I can offer only very general ideas. The main thing, of course, is to try to analyze things of ‘size’ $n$ in terms of things of smaller ‘size’: how can I build things of size $n$ from smaller things? Since this often depends on some specific characteristic – here whether or not the longer thing ends in $2$ (or the shorter in $10$, depending on your point of view) – I often find it helpful to introduce auxiliary functions counting these special cases, as I did here with $a$. The problem then becomes one of getting rid of the auxiliary functions. Here I was able to do it by ... Jun 27, 2015 at 22:07
• ... seeing that $a$ was really just an early instance of $g$. In other problems I’ve had several auxiliary functions running around, and I’ve had to play algebraic games to reduce them to instances of the desired function. One thing that really does help, if you put some effort into it, is going through a considerable variety of problems of this type – not necessarily doing all of them yourself, but seeing how others do them. If you search this site for recurrence relations you’ll find quite a few. Jun 27, 2015 at 22:08