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?