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.

I think we can find a formula by adding any non-X to the end of a good password of length n−1. That way the odd numbered passcodes have potential for two X's side by side...

Answer 1

You can form a valid passcode of length n+1 from a passcode of length n in two ways:
(1) Add a non-X to each valid passcode of length n ((25 new passcodes created))
(2) Add an X to each invalid passcode of length n ((1 new passcode created))

So if P(n) is the number of total (valid or invalid) passcodes of length n, and V(n) is the number of valid passcodes of length n, V(n+1) = 25V(n) + [P(n)-V(n)] = 24V(n) + P(n). And of course, P(n) = 26^n. So V(n+1) = 24V(n) + 26^n.

Answer 2

Does this seem right?