Passwords for a certain computer system are strings of uppercase letters. A valid password must...
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.
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 , or
(b) add an X to the end of a bad password of length . For (b) you can use the Good = Total-Bad trick to count the number of bad passwords of length .
*This is for an Introductory Discrete math course, so any sort of coding will not be helpful and I will not understand.
I also need to figure out the recursive solution for Xn, so if is shown, I have yet to understand how it applies to the recursive solution Xn. If you could PLEASE give me a STEP-FOR-STEP explanation on how this problem and the clues help answer this (throw in some examples as well), it would be so helpful to me. One thing for sure is I do not understand the n-1 part in the clues and how that applies to answering the question. Thus far, I have come up with , but when I set , I end up with 1, which from using paper and pencil, is not correct (x1 should equal 25, not zero)*
Answer & Explanation
Let G(n) represent the number of Good strings of length n, that is the number of strings where there are an even number of X's.
Let B(n) represent the number of Bad strings of length n, that is the number of strings where there are an odd number of X's.
Let T(n) represent the Total number of strings of length n.
It should be clear that , seen from multiplication principle and induction.
It should also be clear that , that and . Alternatively, you could note that and . These will be our "seed" values.
We try to come up with a recursive definition for G(n). To do this, we suppose that we do not know the value for G(n) for the input of n specifically, but we know the value for all inputs strictly less than n (in particular for ).
We recognize that we can count how many good strings of length n there are from the fact that we can construct every good string of length n by using smaller strings. As the hint in the problem suggests, we break into cases based on what the final character of the string is.
Any good string of length n falls into exactly one of the following cases:
- The last character is not an X and the prefix string made up of all characters except the last one is a "good string" of length (which we know exactly how many there are as per our induction hypothesis). There are exactly such strings in this case (pick what the last non-X character it is, and pick which prefix it is, apply multiplication principle).
- The last character is an X and the prefix string made up of all characters except the last one is a "bad string" of length (which we know exactly how many there are as per our induction hypothesis). There are exactly such strings in this case (set the last character as X and then pick which prefix it is, apply multiplication principle).
Noting there is no overlap between the cases and noting that these cases are exhaustive and cover all possibilities, we get the following:
Remembering that we can rewrite the from the above as:
In your post you wrote "But when I set , I end up with 1..."
as expected. Remember that . You probably incorrectly assumed . The empty-string is technically considered to be a string, just like how the empty set is considered to be a set. There is exactly one string of length zero and it has an even number of X's (zero X's to be specific) so it counts as a good string in our problem.
If you wanted to you could continue the problem and come up with a closed form solution for G(n) which is not recursive. At a glance, it will be of the form for some constants c,d which would take some algebra to find.
Instead of finding a recursion formula (of recursion level one), let us give an exact formula (which is a recursion of level zero).
The alphabet has 25 (upper) letters , and also this X: Consider the binomial expansion of
If counts in degree k (i.e. the coefficient of is) the number of words/passwords with exactly k occurences of X. (Because the noncommutative expansion of "shows" all words, and then we formally set .) To isolate all those words with an even number of X's, and prepair them for the counter we build:
Now we set , getting the counter
Examples: , the empty password, in accordance with the formula. , yes, the one-letter-X-password is forbidden. C(2) counts the password XX, and all with two non-X-letters. This is also