# Homework Help: Ternary String recursion relation

1. Apr 17, 2010

### 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.

2. Apr 17, 2010

### 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.

3. Apr 17, 2010

### DorumonSg

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}$$

Last edited: Apr 17, 2010
4. Apr 18, 2010

### rasmhop

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

$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.