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

Consider ternary strings that is strings formed from symbols 0 1 and 2. Let Z_n be thenumber of ternary strings of length n that do not contain substrings 22 and 12. For example for n = 3 allthe 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 satises 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-2how to prorely justify my answer?