
Recurrence Relation
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 nonX to the end of a good word of length n1
or
Add an X to the end of a "notgood" code word of length n1

Let $\displaystyle g_n$ be the number of good passwords of length $\displaystyle n$, and let $\displaystyle b_n$ be the number of bad passwords. The hint allows finding $\displaystyle g_{n+1}$ through $\displaystyle g_n$ and $\displaystyle b_n$. Also, $\displaystyle g_n+b_n$ is the number of all words of length $\displaystyle n$.