2
$\begingroup$

I'm having trouble with this one...I understand others have posted this it seems. However, I don't understand those answers/others some incorrect. I first tried thinking of the different ways this could happen, arranging each case i.e.

case 1: 2 followed by string of n-1 containing 00

case 2: 2 followed by string of n-1 containing 11

case 3: 10 followed by string of n-2 containing 11

case 4: 01 followed by string of n-2 containing 00

case 5: 011 followed by any string of n-3

case 6: 100 followed by any string of n-3

case 6: 00 followed by any string of length n-2

case 7: 11 followed by any string of length n-2

however, not convinced this is correct since im fairly certain there is some overlap/some possiblities im missing.

im assuming it would be a better idea to find ones that DO NOT contain "00" or "11" and subtract that from the total possible 3^n, but im not sure where to start...

$\endgroup$
1
2
$\begingroup$

HINT: You’re right: it’s simpler to work with the complementary set. Let $a_n$ be the number of ternary strings of length $n$ that do not contain $00$ or $11$; I’ll call such strings good strings. Let $b_n$ be the number of these strings that end in $2$.

Suppose that $\sigma$ is a good string of length $n-1$. If $\sigma$ ends in $2$, we can append any of the three characters $0,1$, and $2$ to it to get a good string of length $n$; that accounts for $3b_{n-1}$ good strings of length $n$.

  • If $\sigma$ does not end in $2$, how many different characters can be appended to $\sigma$ to make a good string of length $n$?
  • How many good strings of length $n$ does that account for?

Putting the two pieces together will give you an expression for $a_n$ in terms of $a_{n-1}$ and $b_{n-1}$.

  • Show that $b_n=a_{n-1}$ and use that to get rid of $b_{n-1}$ in the expression just mentioned. The result will be a recurrence for $a_n$.

To finish off, let $c_n=3^n-a_n$, so that $a_n=3^n-c_n$, and substitute into your recurrence to get a recurrence for $c_n$; that’s what you actually want.

Added: An alternative approach is to notice that each good string $\sigma$ of length $n-1$ can be extended in at least $2$ ways to a good string of length $n$. If $\sigma$ ends in $0$ or $1$, it can be extended in only $2$ ways, with $1$ or $2$ in the first case and with $0$ or $2$ in the second. If $\sigma$ ends in $2$, it can be extended in $3$ ways. Thus, every good string of length $n-1$ contributes $2$ good strings of length $n$, for a total of $2a_{n-1}$ strings, and those that end in $2$ contribute a third one as well. Thus, we need to know (in terms of the $a_k$’s) how many good strings of length $n-1$ end in $2$. Each of those strings is obtained by adding a $2$ to a good string of length $n-2$, so there are how many of them?

$\endgroup$
13
  • $\begingroup$ I'm pretty lost once you introduce sigma. Why are we concerned with strings that end with 2? And don't we usually concern ourselves with what the string starts with (as in the cases I wrote above) instead of how they end? $\endgroup$ – ohbrobig Apr 14 '16 at 18:07
  • $\begingroup$ Ok, I understand your comment now...have to look at strings of length n-1 (otherwise we would be ignoring a possible occurence of 00 and 11 between the n-3 term and n-2 term). just wouldn't work...I finished the problem given your suggestions. I get $a_n = 2a_{n-1} + 2a_{n-1} + 3a_{n-1}$. That means the number of string that contain 00 or 11, or $c_n$, is $c_n=3^n-7a_{n-1}$. However, this isn't in terms of $c_n$. I don't get how you can get rid of the $a_{n-1}$ $\endgroup$ – ohbrobig Apr 14 '16 at 19:03
  • $\begingroup$ @ohbrobig: I’m going to add the alternative approach that you ended up using to my answer and then go through and delete all of my comments here; if you delete yours, we can clean this up a bit. $\endgroup$ – Brian M. Scott Apr 14 '16 at 19:35
  • $\begingroup$ So are you saying that it should be $a_n = 2a_{n-1} + 2a_{n-1} + 3a_{n-2}$? $\endgroup$ – ohbrobig Apr 14 '16 at 19:43
  • $\begingroup$ And aren't you supposed to end up with a recursive relation in terms of itself? I.E. $a_n$ in terms of $a_n$? How do we go from are relation which has a $a_n$ as well as $b_n$ $\endgroup$ – ohbrobig Apr 14 '16 at 19:45

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.