-1
$\begingroup$

Find the recurrence relation for number of ternary strings that do not contain two consecutive 0's or 1's.

Strings that contains only 0s, 1s and 2s are called ternary strings.

Answer is $a_n =2 a_{n-1}+a_{n-2}$, but I can't find the reason behind this.

Suppose we have to form such a string of length $n$, then we can start with 2 and then follow with such a string of length of $n-2$. So we will have $a_{n-1}$ different strings.

Other options are when we start with 02 or 12 or 012 or 102....... So how will we get $2a_{n-1}$ in the result?

$\endgroup$
0
$\begingroup$

Call $a_n$ the number of strings of length $n$. Split the cases acording to the last symbol: $u_n$ if it ends in $0$, $v_n$ for ending in $1$ and $w_n$ ending in $2$. We have $a_n = u_n + v_n + w_n$.

Now, a string of length $n + 1$ ending in $0$ is one of length $n$ ending in any symbol with a $0$ appended, so:

$\begin{align} u_{n + 1} &= u_n + v_n + w_n \end{align}$

Coincidentally $a_n = u_{n + 1}$.

If it ends in $1$ or $2$, what came before can't end in that symbol:

$\begin{align} v_{n + 1} &= u_n + w_n \\ w_{n + 1} &= u_n + v_n \\ \end{align}$

This gives:

$\begin{align} u_{n + 1} &= u_n + v_n + w_n \\ v_{n + 1} &= u_n + w_n \\ w_{n + 1} &= u_n + v_n \end{align}$

Initial values are $u_1 = v_1 = w_1 = 1$, and we are interested in $a_n = u_n + v_n + w_n$. Running this "backwards" gives $u_0 = 1$, $v_0 = w_0 = 0$, and $a_0 = 1$, as it should.

Adding up the three equations gives:

$\begin{align} a_{n + 1} &= 3 u_n + 2 v_n + 2 w_n \\ &= u_n + 2 a_n \end{align}$

From before we know $u_n = a_{n - 1}$, and thus:

$\begin{align} a_{n + 1} = 2 a_n + a_{n - 1} \end{align}$

This is equivalent to what you state. We know $a_0 = 1$ from before, and clearly $a_1 = 3$, and your recurrence is complete.

$\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.