0
$\begingroup$

The question asks to create a recurrence relation to determine the number of ternary strings of length n with consecutive 0's or consecutive 1's

I came up with the formula: $a_n = 2a_{n-1}+a_{n-2}+2(3^{n-2})$ with the initial conditions $a_0 = 0$ and $a_1 = 0$

I came up with this formula by just looking at the number of strings that satisfied the question for: $a_0, a_1, a_2$ and $a_3$ and my formula gave the correct answer at each step.

My question is: is this an accurate recurrence relation to determine length n ternary strings with consecutive 0's or consecutive 1's, and if so is there a more mathematical approach to this question?

Thanks

$\endgroup$
1
$\begingroup$

Here’s one approach. Call a ternary sequence good if it contains at least one of the substrings $00$ and $11$ and bad otherwise. Let $b_n$ be the number of bad strings of length $n$; clearly $b_n=3^n-a_n$. Let

  • $c_n$ be the number of bad strings of length $n$ ending in $0$,
  • $d_n$ the number of bad strings of length $n$ ending in $1$, and
  • $e_n$ the number of bad strings of length $n$ ending in $2$;

clearly $b_n=c_n+d_n+e_n$. It’s straightforward to find the following recurrences:

$$\begin{align*} c_n&=d_{n-1}+e_{n-1}=b_{n-1}-c_{n-1}\\ d_n&=c_{n-1}+e_{n-1}=b_{n-1}-d_{n-1}\\ e_n&=b_{n-1}\;. \end{align*}$$

To get a bad string of length $n$ ending in $0$, for instance, you must start with a bad string of length $n-1$ ending in either $1$ or $2$ and tack on a $0$. To get a bad string of length $n$ ending in $2$, you can start with any bad string of length $n-1$ and tack on a $2$.

Adding these three recurrences, we see that

$$\begin{align*} b_n&=3b_{n-1}-c_{n-1}-d_{n-1}\\ &=3b_{n-1}-b_{n-1}+e_{n-1}\\ &=2b_{n-1}+e_{n-1}\\ &=2b_{n-1}+b_{n-2}\;. \end{align*}$$

Now rewrite this recurrence in terms of the the $a_k$s and solve for $a_n$:

$$\begin{align*} 3^n-a_n&=2(3^{n-1}-a_{n-1}+3^{n-2}-a_{n-2}\\ &=2\cdot3^{n-1}+3^{n-2}-2a_{n-1}-a_{n-2}\;, \end{align*}$$

so

$$\begin{align*} a_n&=2a_{n-1}+a_{n-2}+3^n-2\cdot3^{n-1}-3^{n-2}\\ &=2a_{n-1}+a_{n-2}+3^{n-1}-3^{n-2}\\ &=2a_{n-1}+a_{n-2}+2\cdot3^{n-2}\;. \end{align*}$$

The point here is that it’s easier to see the recurrences for $c_n,d_n$, and $b_n$ than to see that for $a_n$ or $b_n$ directly, and it turns out not to be too hard to combine them to get what we want.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.