A coding system encodes messages using strings of octal digits (base 8).?

a codeword is considered valid if and only if it contains an even number of 7's. find a recurrence relation for the number of valid codewords of length n. state initial conditions. solve this recurrence relation usige generating functions.

A coding system encodes messages using strings of octal digits (base 8).?
Let gn be the number of valid codewords of length n, n%26gt;=1.


g1 = 7, because it can be 0,1,2,3,4,5,6,8.


g(n+1) = number of ways to insert one of the other 7 digits into one of the n positions in all the valid codewords of length n + number of ways to insert a digit 7 into one of the n position in all the invalid codewords of length n


= 7n*gn + 1*n*(8^n - gn)


= n*8^n + 6n*gn


= n*8^n + 6n*((n-1)*8^(n-1) + 6(n-1)*g(n-1))


= n*8^n + 6n*(n-1)*8^(n-1) + 6^2*n(n-1)*g(n-1)


= 6^0*n*8^n + 6^1n*(n-1)*8^(n-1) + 6^2*n(n-1)(n-2)*8^(n-2) + ... + 6^n*n(n-1)...(1)*8^(n-n) + 6^n*n!*7


= sum_k_1_n [ n!/(n-k)! * 6^(k-1) * 8^(n-k+1) ] + 6^n*n!*7





I can only do until here, as I can't recall I have ever learnt about generating functions.