Results 1 to 3 of 3

Math Help - find a recurrence relation...

  1. #1
    Member
    Joined
    Sep 2008
    Posts
    103

    find a recurrence relation...

    find a recurrence relation for the number of bit sequences of length n with an even number of 0s

    Thank you so much
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Sep 2008
    Posts
    103
    here is the solution:

    a(n) = 2^n - 2^n
    a(n) = a(n-1) - a(n-2)


    is it true?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by Narek View Post
    here is the solution:
    a(n) = 2^n - 2^n
    a(n) = a(n-1) - a(n-2)
    Of course it is not true. Did you just makeup that answer?
    Do you realize that zero is an even number?
    So a_1 =1; the bit-string “1” contains an even number of zeros.
    And a_2 =2; the bit-strings “11” & “00” contain an even number of zeros.
    Now suppose we think about bit-strings of length 9.
    The 9-bit-strings we want to count contain 0,2,4,6,or 8 zeros.
    We have nine places to put the zeros because the other places will contain ones.
    That is a_9  = \sum\limits_{k = 0}^4 {9 \choose {2k}}  = 256.
    In general a_n  = \sum\limits_{k = 0}^{\left\lfloor {\frac{n}{2}} \right\rfloor } {n \choose {2k}}  = 2^{n - 1}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 9
    Last Post: September 24th 2011, 07:19 AM
  2. find a recurrence relation question
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 29th 2009, 07:03 PM
  3. How to find the limit of recurrence relation
    Posted in the Calculus Forum
    Replies: 1
    Last Post: September 30th 2009, 07:36 AM
  4. Find solution to a recurrence relation...
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 20th 2009, 11:17 AM
  5. find a recurrence relation
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 13th 2008, 09:32 AM

Search Tags


/mathhelpforum @mathhelpforum