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?