# Math Help - recurrence relation problem!

1. ## recurrence relation problem!

hi i am trying to solve this recrrence relation is tough!!
given this question, i had no idea how to define the condition to start!
can someone help me!!? I understand is an-1 for different cases !

A string that contains only 0s, 1s, 2s and 3s is called a quaternary string.

i) Find a recurrence relation for the number of quaternary strings that do not contain two consecutive zeros.

ii)Solve the recurrence relation

2. Originally Posted by yrlim1
A string that contains only 0s, 1s, 2s and 3s is called a quaternary string.
i) Find a recurrence relation for the number of quaternary strings that do not contain two consecutive zeros.
Let $Q_n$ be the number of quaternary strings of length n that do not contain two consecutive zeros.
Do you understand that $Q_1=4~\&~Q_2=15~?$ How and why?
Now how would you count $Q_3~?$
Here is a hint: ‘how many in $Q_2$ end in a zero"?

3. Originally Posted by Plato
Let $Q_n$ be the number of quaternary strings of length n that do not contain two consecutive zeros.
Do you understand that $Q_1=4~\&~Q_2=15~?$ How and why?
Now how would you count $Q_3~?$
Here is a hint: ‘how many in $Q_2$ end in a zero"?
hmm how come Q2 have 15? so much? i thought is mean
Q1
11
10
01
considering all the non-zero case for 1?

Q2
22
21
12

someting like that??

4. Originally Posted by yrlim1
hmm how come Q2 have 15? so much? i thought is mean
Q1
11
10
01
considering all the non-zero case for 1?
Q2
22
21
12
No, the strings that $Q_1$ counts are $0,1,2,3$.

The strings in $Q_2$ are of length two and they are
$01,02,03,10,11,12,13,20,21,22,23,30,31,32,33$.

5. Originally Posted by Plato
No, the strings that $Q_1$ counts are $0,1,2,3$.

The strings in $Q_2$ are of length two and they are
$01,02,03,10,11,12,13,20,21,22,23,30,31,32,33$.
oh!
Q3 would be
001
002
003
110
111
112
113
220
221
222
223
330
331
332
333

and we have to for Q4 also?
how about the occurence of 000? or 00 ?

6. Originally Posted by yrlim1
oh!
Q3 would be
001
002
003
110
111
112
113
220
221
222
223
330
331
332
333
and we have to for Q4 also?
how about the occurence of 000? or 00 ?
You will not get such an answer from me.
Show us some of your own work!

7. Originally Posted by yrlim1
oh!
Q3 would be
001
002
003
110
111
112
113
220
221
222
223
330
331
332
333

and we have to for Q4 also?
how about the occurence of 000? or 00 ?
Read your source materials, look up information on the net...whatever you need to do. Even I can tell that this answer is incorrect and I don't even know the topic! Put some work into it and post your attempt.

-Dan