Were interested in the suite of n values s1 sn were si can b

Were interested in the suite of n values (s_1, ...s_n) were s_i can be 0, 1 or 2. We define a(n), the number of suites of length n while the value 0 doesn\'t appear twice successively. For example for n = 3 a suite could be (0, 2, 1) or (1, 1, 1, 0) but these are not valid (0, 0, 1) or (2, 0, 0) Determine the value of a(1), a(2) are a(3). Show by induction of n so that n superior or equal to 3 (n greaterthanorequalto 3) a(n) = 2_a(n - 1) + 2a(n - 2)

Solution

a) a(1) means the number of suits of length 1

so the values of a(1) can be 0,1,2

The values of a(2) can be be (0,1),(1,0),(1,2),(2,1),(2,0),(0,2),(2,2),(1,1)

the values of a(3) can be (0,1,2),(0,1,0),(0,2,0),(0,1,1),(0,2,1),(0,2,2),(1.0,2),(2,0,1),(1,1,0),(1,0,1),(2,10),(1,2,0),(2,0,2),(2,2,0),(1,2,2),(2,1,2)(1,2,1)(2,1,1),(2,2,1),(1,1,1),(1,1,2),(2,2,2).

b) let us suppose this is correct a(n)= 2a(n-1)+ 2a(n-2)

put n=k,we get a(k)=2a(K-1)+2a(K-2) eqn.1

put n=k+1,we get a(k+1)=2a(k) +2a(k-1) eqn.2

put a=k+2,we get a(k+2)=2a(k+1)+2a(k) eqn3

substitute the value of a(K+1) from eqn.2 & a(k) from eqn.1 inthe eqn. 3,we get

a(k+2)=2{2a(k) + 2a(k-1)} +2a(k)

=4a(k-1)+6a(k)

=4a(k-1)+6{2a(k-1)+2a(k-2)}

=16a(k-1)+12a(k-2)

which proves the supposition