MHB Solving Recursion & Strings Problems

AI Thread Summary
The discussion focuses on solving a recursion problem involving strings formed from the characters "a", "bc", and "cb". Participants are tasked with finding the number of strings of length 3 and 4, denoted as t3 and t4, and establishing a recurrence relation for tn for n ≥ 3. The suggested recurrence relation is tn = tn-1 + 2tn-2, reflecting the ways to construct strings by adding "a" or the combinations of "bc" and "cb". The conversation emphasizes the importance of understanding the construction of strings from previous lengths to derive the recurrence. Overall, the thread provides insights into approaching recursion and string problems effectively.
delc1
Messages
9
Reaction score
0
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.)
 
Physics news on Phys.org
delc1 said:
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.
 
Opalg said:
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.
 
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?
 
Using Opalg's idea, $t_n=t_{n-1}+2t_{n-2}$.
 
I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...
Back
Top