0

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?

Secret
  • 89
  • 8

2 Answers2

1

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

Igor Rivin
  • 25,994
  • 1
  • 19
  • 40
1

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.

Ross Millikan
  • 374,822
  • Somone told me that equation is $$A(n) = 2A_{n-1}+ 2A_{n-1} +3^{n-2}$$, but why $A(n) = 2A_{n-1}$? – Secret Apr 04 '18 at 20:26