Thread: Simple word problem i dont understand.

Hello, Thanks for all your help in the past. I have another problem i don't understand.

The problem text is:
A simplified code system for a computer network consists of code words using the numbers 0,1,2,3,... 7. That is the octal number system. A code word is valid if it contains an even number of 4's.

Sett up an equationfor the number of valid code words of length n.

The answer is supposed to be:

y_n - 6y_(n-1)=8^(n-1), n >= 1

y_0 = 1

The problem is i don't understand how they have arrived at this solution.

(English is not my native language, so i might have gotten some of the math words wrong).

well let's look at some small values of n:

first, the empty code (nothing). this is valid as it contains 0 4's, and 0 is an even number.

next code words of length 1, there are 8 of these. of these only 1 is invalid, the code 4. so we have 8¹ - 1 valid codes.

ok, let's look at code words of length 2. there are 4 cases:

the first digit is 4, the second digit is 4. this is valid (one code).

the first digit is 4, the second digit is not 4. these codes are invalid. there are are 8¹ - 1 codes of this form.

the first digit is not 4, the second digit is 4. these codes are likewise invalid. there are (8¹ - 1)(1) codes of this form.

neither digit is 4. these codes are valid. there are (8¹ - 1)(8¹ - 1) codes of this form.

adding together the valid codes we get: (8¹ - 1)(8¹ - 1) + 1 = 8² - 2(8¹) + 1.

that is y₂ - 6y₁ = 8² - 2(8¹) + 1 - 6(8¹) + 6 = 8² - 8(8¹) + 7 = 7 = 8¹ - 1.

let's look at y₃. count the 4 cases:

first digit is 4, last two digits are a valid code.

first digit is 4, last two digits are an invalid code. <---these are valid codes.

first digit is not 4, last two digits are a valid code. <---these are valid codes.

first digit is not 4, last two digits are an invalid code.

can you think of a way to generalize this procedure?