Thread: Recurrence relation

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

I believe the answer is correct, though the explanation can be improved.

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 you move from strings of length n to strings of length n - 1, it looks like you are removing a digit, not adding it.