Question

Find a recurrence relation for the number of ternary strings of length n that do not contain two consecutive 0s or two consecutive 1s.

Answer 1

Answer:

You can think about it like this: start with a string of length n−1. It's last character is x∈{0,1,2}. If x=0 or x=1, then you have 2 choices for how to finish (either {1,2} if x=0 or {0,2} if x=1). If x=2 then we have 3 choices for how to finish: {0,1,2}. Let's think about what the end of strings look like. I'll let x0 denote that the n−1st element is a 0, x1 to denote that the n−1st element is a 1 and x2 to denote that the n−1st element is a 2. Strings could end in any of the following ways:

x01

x02

x10

x12

x22

x21

x20

Note that if I group the first 6 of these, I have counted 2P(n−1) strings; this is because every one of the strings of length n−1 either ends in a 0, 1 or a 2 and I've counted each of those occurrences twice. And, I still need to count the strings that end in x20 (or the last two digits are 2,0). The number of ways to end in 2,0 is precisely P(n−2) since I can append 2,0 to any string of length n−2. Thus all together there are 2P(n−1)+P(n−2) strings that fit your criteria.