Recurrence equation

profilediakam
Home>Homework Answsers>Computer Science homework help

Consider ternary strings, that is strings formed from symbols 0, 1, and 2. Let Z_n be the

number of ternary strings of length n that do not contain substrings 22 and 12. For example, for n = 3, all

the strings with this property are:

000;001;002;010;011;020;021;100;101;102;110;111;200;201;202;210;211;

and thus Z_3 = 17. (Note that Z_0 = 1, because the empty string satis es the condition.)

(a) Derive a recurrence relation for the numbers Zn. Justify it.

 

I have alredy devired the recurrence equation, I just need a strong justification!!!!

 

Zn=2*Z_n-1+Z_n-2

 

how to prorely justify my answer?

    • 12 years ago
    • 10
    Report issue
    Answer(1)
    profile
    Subhrodip Sengupta
    4.5 (4)
     (Not rated)
    Chat

    Purchase the answer to view it

    blurred-text
    NOT RATED
    • attachment
      zn_recurson_diakam.docx
    • attachment
      zn_recurson_diakam.pdf
    Bids(0)