4
$\begingroup$

I've been stuck on this one for a little bit now. I've looked at the other similar questions on here, but I don't understand the general process for going about forming a recurrence relation from this. How should I go about looking at this problem?

$\endgroup$
  • $\begingroup$ Can the strings contain both two consecutive $0$'s and two consecutive $1$'s? Can they contain a run of more than two consecutive? $\endgroup$ – Marconius Oct 20 '15 at 2:43
4
$\begingroup$

Let $b_n$ be the number of $n$-digit ternary strings which begin with $0$ and contain neither $00$ nor $11$. Let $c_n,d_n$ be the same except starting with $1$ or $2$ respectively. Let $$t_n=b_n+c_n+d_n$$ be the total number of $n$-digit ternary strings which contain neither $00$ nor $11$. What you want is $$a_n=3^n-t_n\ .$$ To find a recurrence for $b_n$ observe that an $n$-digit ternary string which begins with $0$ and contains neither $00$ nor $11$ is

  • $0$, followed by an $(n-1)$-digit string which begins with $1$ and contains neither $00$ nor $11$; or
  • $0$, followed by an $(n-1)$-digit string which begins with $2$ and contains neither $00$ nor $11$.

Therefore $$b_n=c_{n-1}+d_{n-1}\ ;$$ similar arguments give $$c_n=b_{n-1}+d_{n-1}$$ and $$d_n=b_{n-1}+c_{n-1}+d_{n-1}=t_{n-1}\ .$$ Adding all of these gives $$t_n=2t_{n-1}+d_{n-1}$$ and so $$t_n=2t_{n-1}+t_{n-2}\ .$$ Writing in terms of $a_n$, we have $$3^n-a_n=2(3^{n-1}-a_{n-1})+(3^{n-2}-a_{n-2})$$ which simplifies to $$a_n=2a_{n-1}+a_{n-2}+2\times3^{n-2}\ .$$

$\endgroup$
  • $\begingroup$ This way of arriving at a recurrence relation gave a good insight into it $\endgroup$ – jblixr Jan 24 '17 at 1:26
0
$\begingroup$

Above answer by Mr.David is excellent, I would like to tell how I developed intuition. We can see that we need either $2$ consecutive $0$'s or $2$ consecutive $1$'s. So we can place $2$ consecutive $0$'s at the end so for the rest of the $n-2$ positions can have any bit out of $3$ hence $3^{n-2}$ possibilities and same for $2$ consecutive 1's so total of $2\times3^{n-2}$.

Now the core thought. We obtained string ending with $00$ or $11$ but string can end with $01$, $02$, $10$, $12$, $20$, $21$ or $22$. So what we can think is that all $n-1$ length string must be ending with the $0$, $1$ or $2$. Now for $n$'th position we can give $2$ choices for each last bit of $n-1$ string that is if last bit is $1$ then it has $2$ choices $0$ or $2$ (we can not give $1$ as a choice because it will create string ending with $11$ but we already covered that case). Similarly, $0$ will have $2$ choices for $n$'th position, either $1$ or $2$, and also $2$ will have $2$ choices (can be any $2$). But we know for $2$ all the three i.e. $0$, $1$ and $2$ are valid at $n$'th position but we counted only $2$ (any $2$ of your choice). Lets say you had counted string ending with $20$ and $22$. The remaining case that string ends with $21$ can be added by appending $2$ and $1$ to the string of length $n-2$ containing $2$ consecutive $0$'s or $2$ consecutive $1$'s.

So the final intuitive (but right) answer becomes $$a(n) = 2\times3^{n-2} + 2a(n-1) + a(n-2)\text.$$

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