Let \(a_n\) represent the number of bit strings of length \(n\) containing two…

PYQ GATE 2015

Let ana_n represent the number of bit strings of length nn containing two consecutive 1s. What is the recurrence relation for ana_n ?

  1. A.

    an−2+an−1+2n−2a_{n - 2} + a_{n - 1} + 2^{n - 2}

  2. B.

    an−2+2an−1+2n−2a_{n - 2} + 2a_{n - 1} + 2^{n - 2}

  3. C.

    2an−2+an−1+2n−22a_{n - 2} + a_{n - 1} + 2^{n - 2}

  4. D.

    2an−2+2an−1+2n−22a_{n - 2} + 2a_{n - 1} + 2^{n - 2}

Attempted by 35 students.

Sign up free to check your answer

Sign up free

Explore the full course: Zero To Hero

Loading lesson…