For n 1 let ansequence denote the number of ternary strings

For n >= 1, let an(sequence) denote the number of ternary strings (i.e. digits come from the set 0, 1, 2) of length n with the property of having even number of 0 digits (for instance, 012012001 is such a ternary string of length 9 because it has 4 zeros).

1-)What are a1 and a2 ?

2-)Write a recurrence relation for an in terms of an-1.

3-)Use the relation above to find a closed formula for an, for all n >= 1.

Discrete Mathemetics Questions

Solution

1) a1 is of length 1 and having even number of 0 digits

Thus a1 = 1 or a1 = 2

-----------------------------------------------------------------------

a2 can be 00, 11, 12, 21, 22

---------------------------------------------------------------

2) an-1 will contain already even number of 0\'s

Hence for an we can add one digit other than 0, or deleting 1 or 2 and adding 2 zeroes

an = (an-1)1, (an-1)2,1 (an-1), 2(an-1)

--------------------------------------------------

3) a1 = 1 or 2

a2 can be 11 or 12 or 21 or 22 or 00