2

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!

user1176409
  • 1
newtothis1995
  • 23

2 Answers2

5

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.

Chris
  • 488
2

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

Brian M. Scott
  • 616,228
  • You mean $10$ not $01$ in the second paragraph. – pre-kidney Jun 27 '15 at 21:23
  • @pre-kidney: I do indeed; thanks. – Brian M. Scott Jun 27 '15 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. – newtothis1995 Jun 27 '15 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 ... – Brian M. Scott Jun 27 '15 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. – Brian M. Scott Jun 27 '15 at 22:08
  • @BrianM.Scott thanks! – newtothis1995 Jun 27 '15 at 22:13
  • @newtothis1995: You’re welcome. I wish that I could give specific suggestions, but it really does depend a very great deal on the specific problem. – Brian M. Scott Jun 27 '15 at 22:14