Let an be the number of \(n\)-bit strings that do NOT contain two consecutive…

GATE · 2016 · CS · Set 1 · Computer Science & IT

Let an be the number of nn-bit strings that do NOT contain two consecutive 1s. Which one of the following is the recurrence relation for ana_n?

  1. A.

    an=an−1+2an−2a_n = a_{n−1} +2a_{n−2}

  2. B.

    an=an−1+an−2a_n = a_{n−1} +a_{n−2}

  3. C.

    an=2an−1+an−2a_n = 2a_{n−1} +a_{n−2}

  4. D.

    an=2an−1+2an−2a_n = 2a_{n−1} +2a_{n−2}

Attempted by 225 students.

Sign up free to check your answer

Sign up free

Explore the full course: Aptitude For Gate

Loading lesson…