Ternary String recursion relation

[DorumonSg]

I don't understand this at all I have the solution but no idea.

I am suppose to find the recursion relation for consecutive 0 in a ternary string(String that contains only 0, 1 and 2)

So the solution I have is :

Strings starting with 1 = an(The n is the small n for recursion) - 1
Strings startring with 2 = an - 1
Strings starting with 01 = an - 2
Strings starting with 02 = an - 2
Strings starting with 00 = 3^n-2

So the relation is an = 2an-1 + 2an - 2 + 3^n-2 for n >= 3

So how did they get the relation?

Why an - 1? What is the length of the String they base their calculations on?

Example :

I take Strings starting with 1, I can have 10, 11, 12, why an - 1? and not an - 3, all 3 do not have consecutive 0s?

Or if I take the length of the String as 3, I can have 100, 110, 101, 102, 111... so why -1? When I have so many other strings to minus off?

And also for 00,

Where did the 3^n come from?

This is so mind confusing.

 

[rasmhop]

I think you misunderstand what the equations say. The idea is that we let a_n be the number of ternary strings of length n with 00 as a substring. Now if we have a string of length n starting with 1, then it contains consecutive 0 iff the remaining (n-1) characters do. Thus the number of such strings having consecutive 0s is equal to the number of strings of length (n-1) having consecutive 0s, i.e. a_{n-1} (which you wrote as an-1). Similar reasoning holds for the remaining cases. Note that the number of such strings starting with 00 is:
3^{n-2}
I think you may have interpreted the results as a_n-1 and 3^n-2 which is incorrect.

 

[DorumonSg]

I think you misunderstand what the equations say. The idea is that we let a_n be the number of ternary strings of length n with 00 as a substring. Now if we have a string of length n starting with 1, then it contains consecutive 0 iff the remaining (n-1) characters do. Thus the number of such strings having consecutive 0s is equal to the number of strings of length (n-1) having consecutive 0s, i.e. a_{n-1} (which you wrote as an-1). Similar reasoning holds for the remaining cases. Note that the number of such strings starting with 00 is:
3^{n-2}
I think you may have interpreted the results as a_n-1 and 3^n-2 which is incorrect.

Hey wait... even if you say that n - 1 is because iff the consective string is 00... but what if the consecutive string is not 00? it doesn't take that into account?

Okie, but I don't understand why is it for 00 it is 3^{n-2}

 

[rasmhop]

Hey wait... even if you say that n - 1 is because iff the consective string is 00... but what if the consecutive string is not 00? it doesn't take that into account?

I'm not sure exactly what you mean here. Could you elaborate? We are always looking for consequtive 0s (i.e. for 00).

Okie, but I don't understand why is it for 00 it is 3^{n-2}

3^{n-2} is the number of ternary strings of length (n-2). If we know the string starts with 00 we just want the last (n-2) characters to be arbitrary.