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.

$\displaystyle

A_0 = 0

A_1 = 0

A_2 = 1 = 2^2 - 2C1 - 2C2$ ( total number of strings - number of strings that has two 1's or only one '1' )

$\displaystyle

A_3 = 4 = 2^3 - 3C2 - 3C3

$

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. $\displaystyle (2A_n_-_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

$\displaystyle

A_n = 2(A_n_-_1) + n - 1

$