A computer system considers a string of decimal digits a valid codeword if it contains an two '0' digits in it. Let An be the number of valid n-digit codewords. Find a recurrence relation for An.
I don't have the answer in this book.
I solved this in the following way. Please if anyone can validate my answer.
( total number of strings - number of strings that has two 1's or only one '1' )
I have concluded as, when the string length is n, we can have the valid strings of n-1 in two ways. By having 0 in the newly added space or by having 1.
If the n-1 string has X number of strings which have only one '0' in it. Then this also can be added in nth string by adding one more 0 in the new space. And X would be equal to (n-1)C(n-2) = n-1
So the final relation is