Let $a_n$ denote the number of ternary strings of length $n$ that contain either two consecutive $0$'s or two consecutive $1$'s. To derive a recurrence relation for $a_n$, we approach the problem by considering the complementary set of strings.

Step 1: Complementary Counting

Define $b_n$ as the number of ternary strings of length $n$ that do not contain two consecutive $0$'s or $1$'s. Then: $a_n = 3^n - b_n$ where $3^n$ is the total number of ternary strings of length $n$.

Step 2: Finding $b_n$

To count $b_n$, consider how such strings are constructed:

• The first character can be $0, 1,$ or $2$.
• If the first character is $0$, the next character cannot be $0$ (it must be $1$ or $2$).
• Similarly, if the first character is $1$, the next character cannot be $1$ (it must be $0$ or $2$).
• If the first character is $2$, the next character can be any of $0, 1,$ or $2$ because there are no restrictions on consecutive $2$'s.

Thus, the recurrence relation for $b_n$ is: $b_n = 2b_{n-1} + b_{n-2}$ Here:

• $2b_{n-1}$: Accounts for strings starting with $0$ or $1$ followed by a valid string of length $n-1$.
• $b_{n-2}$: Accounts for strings starting with $2$ followed by a valid string of length $n-2$.

Step 3: Relation for $a_n$

Substitute $b_n$ into $a_n$: $a_n = 3^n - b_n$ Using the recurrence for $b_n$, we can now compute $a_n$ for any $n$.

Step 4: Initial Conditions

To complete the recurrence relation, we determine initial conditions:

1. For $n = 1$: All strings are valid, so $b_1 = 3$. Thus, $a_1 = 3^1 - b_1 = 3 - 3 = 0$.
2. For $n = 2$: Valid strings are $\{01, 02, 10, 12, 20, 21, 22\}$, so $b_2 = 7$. Thus, $a_2 = 3^2 - b_2 = 9 - 7 = 2$.

Final Recurrence

The recurrence for $a_n$ is: $a_n = 3^n - (2b_{n-1} + b_{n-2})$ with initial conditions: $b_1 = 3, \quad b_2 = 7, \quad a_1 = 0, \quad a_2 = 2$

Let me know if you'd like to explore specific examples or computations!

---

5 Related Questions:

1. How does the recurrence relation for $b_n$ translate into actual numbers for small $n$?
2. What is the significance of the complementary set in finding $a_n$?
3. How do the constraints on consecutive $0$'s and $1$'s affect the combinatorics of ternary strings?
4. Can this method be generalized to strings over an $k$-ary alphabet?
5. What other problems can be solved using complementary counting?

Tip:

When solving problems involving recurrence relations, identifying complementary cases often simplifies counting and avoids complex case analysis.