Question

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. 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.

Answer 1

For:
n=0: 1 (empty set);
n=1: 25 (26-X letters);
n=2: 25^2 + 1 (two X case);
n=3: 25^3 + 25*3 (two X and a char in any of the 3 places);
This doesn't account for identical letters appearing multiple times though, but I'll have to go so try to figure the rest.

Answer 2

Thank you very much!