1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Ternary String recursion relation

  1. Apr 17, 2010 #1
    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. jcsd
  3. Apr 17, 2010 #2
    I think you misunderstand what the equations say. The idea is that we let [itex]a_n[/itex] 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. [itex]a_{n-1}[/itex] (which you wrote as an-1). Similar reasoning holds for the remaining cases. Note that the number of such strings starting with 00 is:
    I think you may have interpreted the results as [itex]a_n-1[/itex] and [itex]3^n-2[/itex] which is incorrect.
  4. Apr 17, 2010 #3
    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 [tex]3^{n-2}[/tex]
    Last edited: Apr 17, 2010
  5. Apr 18, 2010 #4
    I'm not sure exactly what you mean here. Could you elaborate? We are always looking for consequtive 0s (i.e. for 00).

    [itex]3^{n-2}[/itex] 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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook