# Recurrence relation

• Nov 15th 2010, 11:02 PM
kumaran5555
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.
$
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' )
$
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. $(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
$
A_n = 2(A_n_-_1) + n - 1

$
• Nov 16th 2010, 02:56 AM
emakarov
I believe the answer is correct, though the explanation can be improved.

Quote:

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