Passwords for a certain computer systems are strings of uppercase letters. A val
ID: 1942469 • Letter: P
Question
Passwords for a certain computer systems are strings of uppercase letters. A valid password must contain an even number of X's. Determine a recurrence relations for the number of valid passwords of length n. Note: 0 is an even number, so ABBC is a valid password. 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) ad an X to the end of a bad password of length n - 1. For (b) you can use the Good = Total-Bad trick to count the number of bad passwords of length n - 1.Explanation / Answer
so if we are considering passwords of length n there are 26^n possibilities say f(n) is the number of good passwords and lets say g(n) is number of bad, where as the hint says g(n)+f(n)=26^n, so g(n)=26^n-f(n) so we have to ways to make a good password from a n-1 password. if its already good: add a non-x somewhere if its bad: add an x somewhere. so where can we put either of these letters, we can put it before any of the letters already there or after the last letter, so if there are n-1 letter there there are n places to put this so for passwords that are good at n-1 we have n choices to place and 25 choices of what to place. passwords that are bad we also have n choices we to put but 1 only one option of what to place X. so f(n)=f(n-1)*n*25+g(n-1)*n*1 so f(n)=f(n-1)*n*25+(26^(n-1)-f(n-1))*n Hope that makes sense.