We are tasked with finding a recurrence relation for the number of ternary strings of length $n$ that do not contain consecutive symbols that are the same. A ternary string is a string composed of symbols from the set $\{0, 1, 2\}$, and we want the strings where no two adjacent symbols are the same.

Step 1: Define the Problem

Let $a_n$ represent the number of valid ternary strings of length $n$ that do not contain consecutive symbols that are the same.

Step 2: Build the Recurrence

We can build a recurrence relation by considering how a valid ternary string of length $n$ can be constructed. A string of length $n$ can be obtained by appending a symbol to a valid string of length $n-1$.

• The first step is to choose the first symbol of the string. We have 3 choices: $0, 1,$ or $2$.
• After the first symbol is chosen, the second symbol must be different from the first symbol, leaving 2 choices for the second symbol.
• We continue this pattern for the subsequent symbols.

Thus, each new symbol can be chosen from 2 possibilities (it must be different from the previous symbol).

Step 3: Recursive Structure

The key insight is that:

• A ternary string of length $n$ can be formed by appending a symbol to a valid ternary string of length $n-1$, where the last symbol of the string must differ from the newly added one.

Now, let’s formulate the recurrence relation:

• If we have a valid string of length $n-1$, we can append any of the 2 remaining symbols, making the total number of valid strings of length $n$ twice the number of valid strings of length $n-1$.

Thus, the recurrence relation is: $a_n = 2a_{n-1}$

Step 4: Base Case

We need to define the base case to complete the recurrence:

• For $n = 1$, any ternary string of length 1 is valid, so: $a_1 = 3$ (since we can choose from 3 symbols: 0, 1, or 2).

Final Recurrence Relation

The recurrence relation for the number of ternary strings of length $n$ that do not contain consecutive symbols that are the same is: $a_n = 2a_{n-1}, \quad \text{with} \quad a_1 = 3$

Solution

This recurrence relation defines the sequence. To calculate the number of valid strings for any length $n$, you can iteratively apply the recurrence starting from $a_1 = 3$.

Further Questions:

1. How would you solve for $a_n$ explicitly using this recurrence relation?
2. What is the growth rate of the number of valid ternary strings as $n$ increases?
3. How would the recurrence change if we were considering binary strings (strings of length $n$ over $\{0, 1\}$)?
4. What if the symbols were not restricted to a ternary set, but instead a set of size $k$?
5. How would you compute the number of ternary strings of length $n$ that do not contain any consecutive repeated symbols by hand for small values of $n$?

Tip: You can generalize this recurrence to strings over any alphabet of size $k$. The recurrence would be $a_n = (k-1) a_{n-1}$, with the base case $a_1 = k$.