Solving Recursion & Strings Problems

[delc1]

Hi all,

I cannot understand how to do the following question from a practice test paper and urgently need help!

For each integer n >=1, let tn 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, t1 = 1 ("a" is the only possible string) and t2 = 3 ("aa", "bc" and "cb" are the
possible strings).
(a) Find t3 and t4.
(b) Find a recurrence for tn that holds for all n  3. Explain why your recurrence gives tn.
(You do not have to solve the recurrence.)

 

[Opalg]

Hi all,

I cannot understand how to do the following question from a practice test paper and urgently need help!

For each integer n >=1, let tn 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, t1 = 1 ("a" is the only possible string) and t2 = 3 ("aa", "bc" and "cb" are the
possible strings).
(a) Find t3 and t4.
(b) Find a recurrence for tn that holds for all n 3. Explain why your recurrence gives tn.
(You do not have to solve the recurrence.)

Hi delc1 and welcome to MHB!

Have you been able to make any progress with this problem? For example, in part (a) you are asked to find t3, which is the number of strings of length 3 formed from the ingredients "a", "bc" and "cb". Have you tried to write down all such possible strings? (There are not many, so write them all down and then count how many there are. Then do the same for strings of length 4.)

For part (b), there are two ways to construct a string of length $n$. You can take a string of length $n-1$ and add an "a" at the end of it. Or you can take a string of length $n-2$ and add either a "bc" or a "cb" at the end of it.

 

[delc1]

Hi delc1 and welcome to MHB!

Have you been able to make any progress with this problem? For example, in part (a) you are asked to find t3, which is the number of strings of length 3 formed from the ingredients "a", "bc" and "cb". Have you tried to write down all such possible strings? (There are not many, so write them all down and then count how many there are. Then do the same for strings of length 4.)

For part (b), there are two ways to construct a string of length $n$. You can take a string of length $n-1$ and add an "a" at the end of it. Or you can take a string of length $n-2$ and add either a "bc" or a "cb" at the end of it.

Thank you! Appreciate the help. I understand what is being asked now.

 

[jmath1]

hello, sorry to revive the thread but I am looking at the question and can't make a recursive function for n \ge 3 to save me. I think it has something to do with the n-1 for "a" and n-2 for "bc" and "cb". obviously it has something to do with the previous cases as it is a recursive function. any extra help or hints you could provide would be helpful.

tl;dr do you have any other tips for this question?

 

[Evgeny.Makarov]

Using Opalg's idea, $t_n=t_{n-1}+2t_{n-2}$.