0
$\begingroup$

Q: A string that contains only 0s, 1s and 2s is called a ternary string.

Find a recurrence relation for the number of ternary strings of length n that contain two consecutive 2s.

I don't really understand the question, can someone help me?

$\endgroup$

marked as duplicate by Ross Millikan, Saad, Leucippus, Shailesh, Chris Custer Apr 5 '18 at 1:07

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ Funny that this is the second duplicate asked within an hour. $\endgroup$ – dxiv Apr 4 '18 at 2:24
1
$\begingroup$

The question means: if $T_2(n)$ is the number of strings of length $n,$ which contain two consecutive twos then find some function $f$ such that $T_2(n) = f(T_2(n-1), \dotsc, T_2(1)).$

$\endgroup$
1
$\begingroup$

You define $A(n)$ as the number of ternary strings of length $n$ that contain two $2$s in a row. If you didn't have the restriction there would be $3^n$ ternary strings of length $n$. However, $A(0)=A(1)=0$ because there isn't room for two $2$s in a row. $A(2)=1$ because the only length $2$ string that contains two $2$s in a row is $22$. You are expected to find an equation of the form $A(n)=aA(n-1)+bA(n-2)+$ maybe some more terms by thinking about how you can form a string of length $n$ that has two $2$s. One way is to start with a string of length $n-1$ that already has two $2$s in a row and append any digit.

$\endgroup$
  • $\begingroup$ Somone told me that equation is $$A(n) = 2A_{n-1}+ 2A_{n-1} +3^{n-2}$$, but why $A(n) = 2A_{n-1}$? $\endgroup$ – Secret Apr 4 '18 at 20:26

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