Results 1 to 2 of 2

Math Help - Recurrence relation

  1. #1
    Junior Member
    Joined
    Aug 2010
    Posts
    57

    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.
    <br />
A_0 = 0<br /> <br />
A_1 = 0<br /> <br />
A_2 = 1 = 2^2 - 2C1 - 2C2 ( total number of strings - number of strings that has two 1's or only one '1' )
    <br />
A_3 = 4 = 2^3 - 3C2 - 3C3 <br />
    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
    <br />
A_n = 2(A_n_-_1) + n - 1<br /> <br />
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,504
    Thanks
    765
    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. (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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recurrence relation
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 15th 2011, 11:27 PM
  2. recurrence relation
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: October 18th 2010, 02:15 AM
  3. Recurrence Relation HELP
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 3rd 2009, 01:18 PM
  4. recurrence relation
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 15th 2009, 06:20 PM
  5. Recurrence relation
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 16th 2008, 08:02 AM

Search Tags


/mathhelpforum @mathhelpforum