1

For each integer $n ≥ 1$, let $t_n$ be the number of strings of $n$ letters that can be produced by concatenating (running together) copies of the strings $“a”$, $“bc”$ and $“cb”$.

For example, $t_1$ = $1$ (“a” is the only possible string) and $t_2$ = 3 ($“aa”$, $“bc”$ and $“cb”$ are the possible strings).

(a) Find $t_3$ and $t_4$.

(b) Find a recurrence for $t_n$ that holds for all $n ≥ 3$ Explain why your recurrence gives $t_n$

(You do not have to solve the recurrence.)

Answer I've got so far (by no means do i think this is even close to right)

a) $t_3$ = $"aaa"$, $"bca"$, $"acb"$ ??

dave
  • 103

1 Answers1

1

a) You miss two possibilities. aaa, abc, acb, bca, cba, thus $t_3=5$.

b) $t_4$ is 11. Above 5 with an additional a after it, then those form $t_2$ with bc after it, then those from $t_2$ with cb after it.

c) Can you figure this out yourself using the information in b?

wythagoras
  • 25,026
  • 2
    I'm not sure if this is the right way to go about it but I just sort of picked the pattern (I think)

    $t_n$ = t_(n-1) + 2 x t_(n-2)

    (had trouble with the latex)

     – dave May 03 '15 at 13:30
  • Yes, that is correct! Well done. – wythagoras May 03 '15 at 13:31
  • 1
    what would it mean to explain why my recurrence gives $t_n$ – dave May 03 '15 at 13:46
  • 1
    After the sequences of $t_{n-1}$ you can add an a. After the sequences of $t_{n-2}$ you can add either bc or cb. Since we add bc, cb or a to the end and all sequences we add it to are different, the resulting sequences are different. Can you give an argument yourself why this gives all sequences? – wythagoras May 03 '15 at 13:52