Detailed Explanation of the Recurrence Relation

To find a recurrence relation for the number of ternary strings (strings made of digits $0, 1, 2$) of length $n$ that contain either two consecutive 0s or two consecutive 1s, we use the following steps:

---

Step 1: Define the Problem Clearly

• We are looking for $a_n$: the number of ternary strings of length $n$ with two consecutive 0s or two consecutive 1s.
• For example:
  • For $n = 2$: Strings like "00", "11", and even strings with 2 (e.g., "20") are included if they meet the condition.

---

Step 2: Break Down the Problem

1. Case 1: The string starts with $2$:

   • If the string starts with $2$, the rest of the string (length $n - 1$) must also contain two consecutive 0s or 1s.
   • The number of such strings is $a_{n-1}$.

2. Case 2: The string alternates between 0s and 1s but includes a $2$:

   • For this case, we break the string into three parts:
     1. Part 1: The initial part alternates between $0$ and $1$ (e.g., "010101...").
     2. Part 2: The string includes the digit $2$.
     3. Part 3: After the $2$, the remaining part of the string must contain two consecutive 0s or 1s.
   • Let $k$ represent the length of Part 3 (strings of length $k$ that contain two consecutive 0s or 1s). There are $a_k$ such strings.
   • There are 2 ways to alternate (starting with $0$ or $1$).
   • Therefore, the contribution from this case is $2a_k$ for each $k$.

3. Case 3: The string has no $2s$:

   • If the string has no $2s$, it must alternate between $0$ and $1$ but eventually end with a pair of consecutive 0s or 1s.
   • Let’s break it down:
     • The string alternates for $n - k - 2$ characters (e.g., "010101...").
     • The string ends with a pair of $00$ or $11$.
     • The remaining $k$ characters can be any string of length $k$ (there are $3^k$ possibilities).
   • There are 2 ways to form the consecutive 0s or 1s.
   • The contribution is $2 \cdot 3^k$ for each $k$.

---

Step 3: Add All the Possibilities

The total number of strings is the sum of the contributions from all cases: $a_n = a_{n-1} + \sum_{k=0}^{n-2} \left( 2a_k + 2 \cdot 3^k \right)$ Using the formula for the sum of a geometric series, the second part simplifies to: $a_n = a_{n-1} + 2a_{n-2} + 2a_{n-3} + \dots + 2a_0 + 3^{n-1} - 1$

---

Step 4: Simplify the Recurrence Relation

To simplify further, notice that: $a_n - a_{n-1} = 2 \cdot 3^{n-2}$ Rewriting gives a closed form recurrence relation: $a_n = 2a_{n-1} + a_{n-2} + 2 \cdot 3^{n-2}$

---

Examples with Steps

Example 1: $n = 2$

• Strings of length $2$: "00", "01", "02", "10", "11", "12", "20", "21", "22".
• $a_2 = 3$ because only "00", "11", and "22" have consecutive 0s or 1s.

---

Example 2: $n = 3$

1. Case 1: Start with $2$: $a_2 = 3$.
2. Case 2: Alternating (e.g., "010" or "101"), then include $2$:
   • Example: "0102" or "1012".
   • Contribution is $2a_1 = 2 \cdot 1 = 2$.
3. Case 3: Ends with $00$ or $11$:
   • Example: "01000" or "10111".
   • Contribution is $2 \cdot 3^1 = 6$.
4. Total: $a_3 = a_2 + 2a_1 + 2 \cdot 3^1 = 3 + 2 \cdot 1 + 6 = 11$

---

Step 5: Key Intuition for Alternating Parts

• Alternating strings like "01010..." switch between $0$ and $1$.
• If we start with $0$, the next must be $1$, then $0$, etc.
• This pattern breaks when a $2$ is added or when the sequence ends with "00" or "11".

---

Tip

Always break the problem into small cases and think of how the first part of the string affects the rest.