Let be the number of good passwords of length , and let be the number of bad passwords. The hint allows finding through and . Also, is the number of all words of length .
Passwords for a certain computer system are strings of uppercase letters. A valid password must contain an even number of X's. Determine a recurrence relation for the number of valid passwords of length n.
Hint: Either add a non-X to the end of a good word of length n-1
Add an X to the end of a "not-good" code word of length n-1