Thread: Applications of Recurrence Relations: Ternary string question

1. Applications of Recurrence Relations: Ternary string question

I'm having trouble tackling this problem,

"Find a recurrence relation for the number of ternary strings of length n that contain two consecutive 0s"

I was wondering where a good place to start is with questions like these

2. Re: Applications of Recurrence Relations: Ternary string question

What do you mean by "ternary string"? Is that a string where every character may be one of three possible values?

3. Re: Applications of Recurrence Relations: Ternary string question

Yes it's like a binary string except there can be a 2, so the possible values are 0, 1, 2

5. Re: Applications of Recurrence Relations: Ternary string question

Originally Posted by masonD
I'm having trouble tackling this problem,
"Find a recurrence relation for the number of ternary strings of length n that contain two consecutive 0s"
I was wondering where a good place to start is with questions like these
As stated this is what we let $\mathcal{T}_n$ be the collection of ternary strings of length $n$ that contain two consecutive 0s".
We denote the number of elements in $\mathcal{T}_n$ by ${t}_n$.
$\mathcal{T}_1=\emptyset$ so $t_1=0$
$\mathcal{T}_2=\{00\}$ so $t_2=1$
$\mathcal{T}_3=\{~000,~100,~200,001,002\}$ so $t_3=4$

Be sure that I constructed those correctly & that I counted all.
How was $\mathcal{T}_3$ constructed using $\mathcal{T}_1,~\&~\mathcal{T}_2~?$

What does $\mathcal{T}_4$ look like and how is it constructed?

6. Re: Applications of Recurrence Relations: Ternary string question

Originally Posted by Plato
As stated this is what we let $\mathcal{T}_n$ be the collection of ternary strings of length $n$ that contain two consecutive 0s".
We denote the number of elements in $\mathcal{T}_n$ by ${t}_n$.
$\mathcal{T}_1=\emptyset$ so $t_1=0$
$\mathcal{T}_2=\{00\}$ so $t_2=1$
$\mathcal{T}_3=\{~000,~100,~200,001,002\}$ so $t_3=4$

Be sure that I constructed those correctly & that I counted all.
How was $\mathcal{T}_3$ constructed using $\mathcal{T}_1,~\&~\mathcal{T}_2~?$

What does $\mathcal{T}_4$ look like and how is it constructed?
take another look

$t_3=5$

7. Re: Applications of Recurrence Relations: Ternary string question

Originally Posted by romsek
take another look

$t_3=5$
Thank you. I cannot even count to 5!