Passwords for a certain computer system are strings of uppercase letters. A vali

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. For (b) you can use the

Explanation / Answer

for n=1:25 for n=2:25*25+1 for n=3:(25*25+1)*25+25*1 for n=4:((25*25+1)*25+25*1)*25+(25*25+1) so the recursive relation is the previous term*25 plus the term 2 before. So An=(An-1)*25+An-2 those n, n-1, and n-2 are all subscripts

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---