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}$.
 
Hello, I'm joining this forum to ask two questions which have nagged me for some time. They both are presumed obvious, yet don't make sense to me. Nobody will explain their positions, which is...uh...aka science. I also have a thread for the other question. But this one involves probability, known as the Monty Hall Problem. Please see any number of YouTube videos on this for an explanation, I'll leave it to them to explain it. I question the predicate of all those who answer this...
I'm taking a look at intuitionistic propositional logic (IPL). Basically it exclude Double Negation Elimination (DNE) from the set of axiom schemas replacing it with Ex falso quodlibet: ⊥ → p for any proposition p (including both atomic and composite propositions). In IPL, for instance, the Law of Excluded Middle (LEM) p ∨ ¬p is no longer a theorem. My question: aside from the logic formal perspective, is IPL supposed to model/address some specific "kind of world" ? Thanks.
I was reading a Bachelor thesis on Peano Arithmetic (PA). PA has the following axioms (not including the induction schema): $$\begin{align} & (A1) ~~~~ \forall x \neg (x + 1 = 0) \nonumber \\ & (A2) ~~~~ \forall xy (x + 1 =y + 1 \to x = y) \nonumber \\ & (A3) ~~~~ \forall x (x + 0 = x) \nonumber \\ & (A4) ~~~~ \forall xy (x + (y +1) = (x + y ) + 1) \nonumber \\ & (A5) ~~~~ \forall x (x \cdot 0 = 0) \nonumber \\ & (A6) ~~~~ \forall xy (x \cdot (y + 1) = (x \cdot y) + x) \nonumber...
Back
Top