$(3)$ Passwords for a certain computer system are strings of uppercase letters. A valid password must contain an even number of $x\text{'}$s$.$ Determine a recurrence relation for the number of valid passwords of length $n.$ Note: $0$ is an even number, so ABBC is a valid password. This counting problem is pretty tricky. Here's a good way to think about it: to make a good password of length $n$ you can either $($a$)$ add any non$-x$ to the end of a good password of length $n-1,$ or $($b$)$ add an $x$ to the end of a bad password of length $n-1.$ For $($b$)$ you can use the Good $=$ Total$-$Bad trick to count the number of bad passwords of length $n-1.$