# Recurrence relation

• Nov 15th 2010, 10: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.
\$\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

\$
• Nov 16th 2010, 01: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.\$\displaystyle (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.