1

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

Eliza Q
  • 31
  • 1
    Welcome to MathSE. When you pose a question here, it is expected that you include your own thoughts on the problem. Please edit your question to show what you have attempted and explain where you are stuck so that you receive responses that address the specific difficulties you are encountering. This tutorial explains how to typeset mathematics on this site. – N. F. Taussig Nov 12 '18 at 01:08
  • S2 is more than $5$. You can have one six and one of five other numbers in either order. You should also define the a function for the number of $n$ digit strings with an even number of $6$s. You can then find a recurrence between them. – Ross Millikan Nov 12 '18 at 01:40

0 Answers0