Find a recurrence relation for a ternary string of length $n$ that contains at least one $1$ and at least one two.

Question

Let $A_n$ represent the number of ternary strings of length $n$ that contain at least one '1' and at least one '2'.

My reasoning is that appending a $0$ to a valid $(n-1)$-length string maintains its validity. However, appending a '1' or a '2' requires further consideration.

If I append a '1' to an $(n-1)$-length string, I need to evaluate the sequences ending in '01', '11', and '21'. For sequences ending in '01', there are $A_{n-2}$ valid strings. For '11', I need to consider additional subcases. For '21', there are $3^{n-2}$ possible strings.

A similar analysis applies if I append a '2' to the end of an $(n-1)$-length string.

This leads me to the recurrence relation $A_n = 2A_{n-1} + A_{n-2} + 2 \times 3^{n-2}$. Is my logic correct?

Answer 1

Direct way to compute $A_n$: The complement is "ternary strings of length $n$ that either have no $1$s or have no $2$s" which has cardinality $2^n + 2^n - 1 = 2^{n+1}-1$. So $A_n = 3^n - 2^{n+1} + 1$.

---

This does not seem to satisfy your recursion, so something is wrong.

$$3^n-2^{n+1} +1 \ne 2 (3^{n-1} - 2^n + 1) + (3^{n-2} - 2^{n-1} + 1) + 2 \cdot 3^{n-2}.$$

---

Here is one way to set up a recursion. A valid string of length $n$ follows one of the following cases.

• A valid string of length $n-1$, followed by any character ($0$, $1$, or $2$).
• A string of length $n-1$ that has no $1$s but at least one $2$, followed by a $1$.
• A string of length $n-1$ that has no $2$s but at least one $1$, followed by a $2$.

This yields $A_n = 3 A_{n-1} + 1 \cdot (2^{n-1} - 1) + 1 \cdot (2^{n-1} - 1) = 3 A_{n-1} + 2^n - 2$. To check that the exact expression of $A_n$ satisfies this, note that $$3^n - 2^{n+1} + 1 = 3(3^{n-1} - 2^n + 1) + 2^n - 2.$$