3
$\begingroup$

I attempted this problem and this is what I have so far:

First, I considered the possible "cases".

If the string starts with $00$ or $11$, then the rest can be anything so there are $2\cdot 3^{n-2}$ such strings.

If the string starts with $2$, then there are $n-1$ strings that contain two consecutive $0$s or $1$s.

If the string starts with $22$, then there are $n-2$ strings that contain two consecutive $0$s or $1$s.

I came up with the recurrence relation: $$a_n=a_{n-1}+a_{n-2}+2\cdot 3^{n-1}.$$ However, the solution in my textbook says it is actually $$a_n=2a_{n-1}+a_{n-2}+2\cdot 3^{n-2}.$$ I can't seem to figure out why $a_{n-1}$ is multiplied by two.

$\endgroup$
  • 1
    $\begingroup$ Read again what you have written: If the string starts with $2$, why there should be only $n-1$ admissible continuations? $\endgroup$ – Christian Blatter Nov 19 '17 at 18:43
  • $\begingroup$ Here either stands for $\text{OR}$ or for $\text{XOR}$? (I guess the latter, but I am not that confident in this linguistic nuances). $\endgroup$ – Jack D'Aurizio Nov 19 '17 at 20:09
  • $\begingroup$ Possible duplicates: math.stackexchange.com/questions/1741933/… math.stackexchange.com/questions/1488507/… $\endgroup$ – Robert Z Nov 19 '17 at 20:29
  • $\begingroup$ @penyou: I think you mean $a_{n-1}$ instead of $n-1$ and $a_{n-2}$ instead of $n-2$ in the cases of strings starting with $2$ resp. $22$. $\endgroup$ – Markus Scheuer Nov 19 '17 at 21:24
1
$\begingroup$

We can derive the recurrence relation for $a_n$ as follows:

  • 00|11: A string may start with either $00$ or $11$ leaving $\color{blue}{2\cdot 3^{n-2}}$ ways for the remaining substring of length $n-2$.

  • 22: A string may start with $22$ leaving $\color{blue}{a_{n-2}}$ ways for the remaining substring of length $n-2$.

In all the other cases the string starts

  • 0(1|2): either with $0$ followed by $1$ or $2$

  • 1(0|2): or with $1$ followed by $0$ or $2$

  • 2(0|1): or with $2$ followed by $0$ or $1$.

In each of these three cases the first character is followed by one of two characters leaving $\color{blue}{2a_{n-1}}$ ways for the remaining substring of length $n-1$.

We conclude a recurrence relation for $a_n$ is \begin{align*} a_n&=2a_{n-1}+a_{n-2}+3\cdot 2^{n-2}\qquad\qquad n\geq 4\\ a_2&=2\\ a_3&=10 \end{align*}

The base cases $a_2=2$ and $a_3=10$ can be manually verified by \begin{align*} &n=2:\qquad 00,11\\ &n=3:\qquad 000,001,002,011,100,110,111,112,200,211 \end{align*}

$\endgroup$
0
$\begingroup$

Your argument is not correct because the case "the string starts with 2" include the case "the string starts with 22".

I think it's easier to consider the "complement" sequence.

Let $A_n$, $B_n$ and $C_n$ be the number of ternary strings of length $n$ that contain no consecutive $0$s and no consecutive $1$s, and which start with $0$, $1$, and $2$ respectively. Then $a_n=3^n-(A_n+B_n+C_n)$.

We have the linear recurrences for $n\geq 2$: $$\begin{cases} A_{n}&=B_{n-1}+C_{n-1}\quad &\text{(after a $0$ we can have $1$ or $2$)}\\ B_{n}&=A_{n-1}+C_{n-1}\quad &\text{(after a $1$ we can have $0$ or $2$)}\\ C_{n}&=A_{n-1}+B_{n-1}+C_{n-1}\quad &\text{(after a $2$ we can have $0$, $1$ or $2$)} \end{cases} $$ and it follows that $$ \begin{cases} A_{n}=2A_{n-1}+A_{n-2}\\ B_{n}=2B_{n-1}+B_{n-2}\\ C_{n}=2C_{n-1}+C_{n-2} \end{cases}$$ and by summing them we obtain $$A_{n}+B_{n}+C_{n}= 2(A_{n-1}+B_{n-1}+C_{n-1})+(A_{n-2}+B_{n-2}+C_{n-2}).$$ Hence $$\begin{align} a_{n}&=3^{n}-(A_{n}+B_{n}+C_{n})\\ &= 3^{n}-(2(A_{n-1}+B_{n-1}+C_{n-1})+(A_{n-2}+B_{n-2}+C_{n-2}))\\ &=3^{n}-2(3^{n-1}-a_{n-1})-(3^{n-2}-a_{n-2})\\ &=2a_{n-1}+a_{n-2}+2\cdot 3^{n-2}. \end{align}$$ Since $a_1=0$, and $a_2=2$, it follows that the first terms of the sequence (see OEIS's A193519) are $$0,2,10,40,144,490,1610,5168, 16320, 50930.$$

$\endgroup$
  • $\begingroup$ Could you explain this part in your math: $a_{n+1}=3^{n+1}-(A_{n+1}+B_{n+1}+C_{n+1})= 3^{n+1}-(2(A_{n}+B_{n}+C_{n})+(A_{n-1}+B_{n-1}+C_{n-1}))$ $\endgroup$ – penyou Nov 19 '17 at 19:38
  • $\begingroup$ Note that $(A_n+B_n+C_n)=3^n-a_n$. Could you please check the answer of your book? It should be $a_n=2a_{n-1}+a_{n-2}+2\cdot 3^{n-2}$. $\endgroup$ – Robert Z Nov 19 '17 at 19:41
  • $\begingroup$ Answer in textbook: $a_{n} = 2a_{n-1} + a_{n-2} + 2*3^{n-2}$ $\endgroup$ – penyou Nov 19 '17 at 19:42
  • $\begingroup$ In the question you wrote a different thing... Now it is correct. $\endgroup$ – Robert Z Nov 19 '17 at 19:47
  • $\begingroup$ By summing the recurrences for $A_n$, $B_n$ and $C_n$, we find that $A_n+B_n+C_n$ satisfies the same recurrence. $\endgroup$ – Robert Z Nov 19 '17 at 19:56

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.