0
$\begingroup$

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 n − 1, or

(b) add 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.

*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 Xn+1 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 Xn= 24(x(n-1)) + 26^(n-1), but when I set n=1, I end up with 1, which from using paper and pencil, is not correct (x1 should equal 25, not zero)*

$\endgroup$
  • $\begingroup$ $x_0 = 1$ not $0$. There is one valid string of length zero, the empty string: " " $\endgroup$ – JMoravitz Oct 18 '18 at 4:16
0
$\begingroup$

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 $T(n) = G(n)+B(n) = 26^n$, seen from multiplication principle and induction.

It should also be clear that $T(1)=26$, that $G(1)=25$ and $B(1)=1$. Alternatively, you could note that $T(0)=G(0)=1$ and $B(0)=0$. 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 $n-1$).

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 $n-1$ (which we know exactly how many there are as per our induction hypothesis). There are exactly $25\times G(n-1)$ 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 $n-1$ (which we know exactly how many there are as per our induction hypothesis). There are exactly $1\times B(n-1)$ 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:

$$G(n) = 25\times G(n-1) + 1\times B(n-1)$$

Remembering that $T(n-1) = G(n-1) + B(n-1) = 26^{n-1}$ we can rewrite the $B(n-1)$ from the above as:

$$G(n) = 25\times G(n-1) + (26^{n-1} - G(n-1))$$ $$G(n) = 24\times G(n-1) + 26^{n-1}$$

In your post you wrote "But when I set $n=1$, I end up with $1$..."

$G(1) = 24\times G(1-1) + 26^{1-1} = 24\times G(0) + 26^0 = 24\times 1 + 1 = 25$ as expected. Remember that $G(0)=1$. You probably incorrectly assumed $G(0)=0$. 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 $G(n) = c\cdot 24^n + d\cdot 26^n$ for some constants $c,d$ which would take some algebra to find.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you so much for the detailed explanation! I did have one question in relation to G(n)=25×G(n−1)+1×B(n−1). Shouldn't it be T(n)=25×G(n−1)+1×B(n−1) instead of G(n)=25×G(n−1)+1×B(n−1). To me, the one provided would actually equal the total number of passwords, not the number of good passwords. Am I missing something with regards to how notation is being used? $\endgroup$ – Botonox03 Oct 18 '18 at 14:05
  • $\begingroup$ It is indeed only the good that it counts. T(n) = 26 T(n-1) = 26 G(n-1) + 26 B(n-1) is strictly greater than the above. In constructing G(n) using smaller strings, we either took an even number of Xs in the prefix and attached a non-X to the end, even+0 is still even, or we took a prefix with an odd number of Xs and add one X to the end, odd+1=even. In both cases we end with an even number of Xs. $\endgroup$ – JMoravitz Oct 18 '18 at 16:40
0
$\begingroup$

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 $\ne X$, and also this $X$: Consider the binomial expansion of $$ (25+X)^n\ . $$ If counts in degree $k$ (i.e. the coefficient of $X^k$ is) the number of words/passwords with exactly $k$ occurences of $X$. (Because the noncommutative expansion of $(A+B+\dots+W+Y+Z\qquad +X)^n$ "shows" all words, and then we formally set $A=B=\dots=W=Y=Z=1$.) To isolate all those words with an even number of $X$'s, and prepair them for the counter we build: $$\frac 12\Big(\ (25+X)^n+(25-X)^n\ \Big)\ .$$ Now we set $X=1$, getting the counter $$C(n)=\frac 12\left( 26^n+24^n\right)\ .$$


Examples: $C(0)=1$, the empty password, in accordance with the formula. $C(1)=(26+24)/2=25$, yes, the one-letter-$X$-password is forbidden. $C(2)$ counts the password $XX$, and all $\alpha\beta$ with two $\alpha,\beta$ non-$X$-letters. This is also $\frac 12(26^2+24^2)=\frac 12((25+1)^2+(25-1)^2)=\frac 12\sum_\pm(25^2\pm2\cdot25+1 ^2)=25^2+1^2=C(2)$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.