Project ForgeDiscrete Mathematics
Probability & Combinatorics
GATE 2015
Expert
Let aₙ represent the number of bit strings of length n containing two consecutive 1s. What is the recurrence relation for aₙ?
- a(n−2) + a(n−1) + 2^(n−2)
- Ba(n−2) + 2a(n−1) + 2^(n−2)
- C2a(n−2) + a(n−1) + 2^(n−2)
- D2a(n−2) + 2a(n−1) + 2^(n−2)
Explanation
Split by the string's start: if it starts with 0, the remaining n−1 bits must independently contain '11' — contributing a(n−1) strings. If it starts with 10, the remaining n−2 bits must contain '11' — contributing a(n−2) strings. If it starts with 11, the '11' pattern is already satisfied by the first two bits, and the remaining n−2 bits can be ANYTHING — contributing 2^(n−2) strings. Total: a(n) = a(n−1) + a(n−2) + 2^(n−2).
Source: GATE CS 2015 (Session 1 / 7th Feb Shift 1) (2015)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.