To derive the recurrence relation $a_n = 2a_{n-1} + 3^{n-1}$, we consider the number of ternary strings of length $n$ (strings formed using the symbols $0, 1, 2$) that contain at least one instance of two consecutive symbols being the same. Let's explain this step by step:

---

Step 1: Understanding the problem

1. Definition: $a_n$ represents the number of ternary strings of length $n$ that contain two consecutive symbols that are the same.
2. Goal: Derive a recurrence relation that expresses $a_n$ in terms of previous terms ($a_{n-1}$, $a_{n-2}$, etc.).

---

Step 2: Counting valid strings of length $n$

To construct a string of length $n$, we can follow two cases:

Case 1: Start with two different symbols

• The first symbol can be any of $3$ choices ($0, 1,$ or $2$).
• The second symbol must be different from the first, so there are $2$ choices.
• The rest of the string (length $n-1$) must include at least one pair of consecutive identical symbols.

Using symmetry, the number of such strings is evenly distributed among the three starting symbols. Therefore: $\text{Strings of this form starting with any specific symbol } = \frac{2a_{n-1}}{3}.$ Thus, the total number of strings in this case is: $3 \cdot \frac{2a_{n-1}}{3} = 2a_{n-1}.$

Case 2: Start with two identical symbols

• The first two symbols are the same. The first symbol has $3$ choices.
• The remaining $n-2$ positions can contain any ternary string of length $n-2$, i.e., there are $3^{n-2}$ such strings.

Thus, the total number of strings in this case is: $3 \cdot 3^{n-2} = 3^{n-1}.$

---

Step 3: Combining the cases

By adding the counts from the two cases, the total number of strings $a_n$ satisfying the condition is: $a_n = 2a_{n-1} + 3^{n-1}.$

This recurrence relation is valid for $n \geq 2$.

---

Step 4: Base case

For $n = 1$, a single symbol cannot have consecutive symbols, so $a_1 = 0$.

---

Step 5: Final recurrence

$a_n = 2a_{n-1} + 3^{n-1}, \quad \text{for } n \geq 2.$ $a_1 = 0.$

---

Key Points of the Explanation:

1. Symmetry is exploited to distribute the cases evenly among the three symbols.
2. The two cases—starting with different symbols and starting with identical symbols—cover all possibilities for constructing the strings.
3. The recurrence relation combines the counts from these cases.

---

Questions for Further Understanding:

1. How do we verify the recurrence relation using small values of $n$?
2. What is the role of symmetry in simplifying the problem?
3. How does the term $3^{n-1}$ represent the strings where the first two symbols are identical?
4. What adjustments would we make if the strings were binary instead of ternary?
5. How does $a_n$ compare to the total number of ternary strings of length $n$?

Tip:

When solving problems involving recurrence relations, consider breaking down the cases systematically and ensure all possibilities are accounted for. Symmetry often simplifies calculations significantly.