MA375: Solution to a homework problem from this week or last week's homework
Spring 2009, Prof. Walther
7.1 #30
This problem is a lot like 24. A ternary string means that instead of the string just containing 2 variables (0 and 1), it contains 3 (0,1,and 2).
a) You start off with the good string: and either the first is a zero or not a zero. If it is not a zero, it could be either a 1 or a 2 so there are 2(a_n-1) ways of this happening. Then if the first is a zero then the second can be a zero or not a zero. If not a zero again there are two ways of this happening so 2(a_n-2) and then if the second is a zero we have 3^n-2
so the recurrence equation is: a_n= 2a_n-1 + 2a_n-2 + 3^n-2
b) initial conditions are a1=0 a2=1 a3=1
c) A(4)=2+2+ 3^2= 13
A(5)=2(13)+ 2 + 3^3=55 A(6)=2(55) = 2(13) + 3^4= 217 ways
