# Math Help - Recurrence Relation

1. ## 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 non-X to the end of a good word of length n-1
or
Add an X to the end of a "not-good" code word of length n-1

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