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