Results 1 to 5 of 5

Math Help - New to recursion and have no idea how to solve this problem

  1. #1
    Newbie
    Joined
    Jun 2011
    Posts
    2

    New to recursion and have no idea how to solve this problem

    For each integer n >= 0, let a(n) be the number of bit strings of length n that do not contain the pattern 101.

    a.) Show that a(k) = a(k-1) + a(k-3) + a(k-4) + ... + a(0) + 2, for all integers k>= 3.

    b.) Use the result of part (a) to show that if k >= 3, then a(k) = 2a(k-1) - a(k-2) + a(k-3)

    **everything in parenthesis is treated as a subscript

    This question is totally unlike anything else from this section of the book. I really have no idea where to even start. Part a almost looks like I could do induction but I don't know if that would be correct. The only thing I've done so far is I wrote out the first couple of bit length (don't even know if I'm supposed to do this) and came up with:

    Length 0: ∊
    Length 1: 0, 1
    Length 2: 11, 10, 01, 00
    Length 3: 111, 110, 100, 000, 001, 011, 010 (101 is excluded, obviously).

    I also understand that a recursive formula I can write is

    a(k) = 2a(k-1) + 2a(k-2) + a(k-3) (I think, not sure if this is correct)
    Last edited by AkoCham; June 17th 2011 at 11:01 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: New to recursion and have no idea how to solve this problem

    are you sure you have the formula in part a) correct?

    a3 = 7, but a2 + a0 + 2 = 6.
    Last edited by Deveno; June 17th 2011 at 01:37 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    May 2011
    From
    Sacramento, CA
    Posts
    165

    Re: New to recursion and have no idea how to solve this problem

    Induction was my first instinct, but I think regardless you will have to relate the various a(i). To facilitate that, each a(i) has 2^i possible bit sequences, of which we'll have to exclude a certain number that include the 101 pattern. You already exposed this in your first four cases: length 0 is the empty bit string, length 1 is (0, 1), length 2 is (11, 10, 01, 00), etc. My intuition is that there is something to be explored when we, say, add a(k-3) + a(k-4), and the like when we think of it in terms of 2^k less the 101 bit sequences. I assume the 101 pattern showing up anywhere in a string (e.g., 100101011 would be excluded) rules it out. So, in a string of length k, how many of the 2^k will be excluded? Ultimately, that is what I think this algorithm is expressing by putting it in terms of how many are excluded from lesser length bit strings. Therefore, to facilitate the solution, we will need to know how many are excluded along the way, and the reason we're concerned with k greater than 2 is because, as you show, exclusion only begins at length 3 sequences.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jun 2011
    Posts
    2

    Re: New to recursion and have no idea how to solve this problem

    I believe the formula is part a is correct. I have uploaded a picture of the actual problem:

    http://i.imgur.com/MDsoz.jpg
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    May 2011
    From
    Sacramento, CA
    Posts
    165

    Re: New to recursion and have no idea how to solve this problem

    One thing you might want to try is write the expression for a(k-1) in the form of a(k), and so on for the rest of the a(i)'s. Then by substituting the values for each a(i) you might have something more manageable, maybe. Just something I thought you might want to explore.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. I want the idea to solve this queation
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: May 30th 2010, 08:29 AM
  2. have no idea how solve this?
    Posted in the Algebra Forum
    Replies: 3
    Last Post: May 18th 2010, 08:14 PM
  3. I have no idea what this is called or how to solve
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: May 1st 2010, 08:46 PM
  4. Solve a homogenous recursion
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: May 22nd 2009, 07:33 AM
  5. congruence [I have no idea how to solve this]
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 27th 2008, 05:55 PM

Search Tags


/mathhelpforum @mathhelpforum