Let an be the number of \(n\)-bit strings that do NOT contain two consecutive…
2016
Let an be the number of \(n\)-bit strings that do NOT contain two consecutive 1s. Which one of the following is the recurrence relation for \(a_n\)?
- A.
\(a_n = a_{n−1} +2a_{n−2}\) - B.
\(a_n = a_{n−1} +a_{n−2}\) - C.
\(a_n = 2a_{n−1} +a_{n−2}\) - D.
\(a_n = 2a_{n−1} +2a_{n−2}\)
Attempted by 42 students.
Show answer & explanation
Correct answer: B
Answer: a_n = a_{n-1} + a_{n-2}.
Reason: Consider the first bit of an n-bit string that does not contain consecutive 1s.
If the first bit is 0: the remaining n-1 bits can be any valid string, giving a_{n-1} possibilities.
If the first bit is 1: the second bit must be 0, so the first two bits are "10" and the remaining n-2 bits can be any valid string, giving a_{n-2} possibilities.
Adding the two cases gives a_n = a_{n-1} + a_{n-2}.
Base cases: a_1 = 2 (strings: 0, 1) and a_2 = 3 (strings: 00, 01, 10).
Observation: These numbers follow the Fibonacci sequence, with a_n = F_{n+2} if F_0 = 0 and F_1 = 1.