A coding system encodes messages using strings of base 7 digits. A codeword is considered valid if and only if it contains an even number of 6s.
i. Find a recurrence relation for the number of valid codewords of length n. State initial conditions.
ii. Solve this recurrence relation using generating functions.
This is how far i've gotten using a previous example
Set of strings of {0, 1, 2,3,4,5,6} Valid – String contains an odd number of 6s e.g. 643210 or 654606 or 6 Let n be the length of the codeword Sn be the number of valid codewords of length n or Sn is the number of codewords of length n with an odd number of 6s i.e. Sn-1 is the number of codewords of length n-1 with an odd number of 6s Sn-2 is the number of codewords of length n-2 with an odd number of 6s
By Calculation
S0 = 0
S1 = 3
S2 = 5