Gate CS-2015-1 Question Paper With Solutions

Q. 59 Let a_n represent the number of bit strings of length n containing two consecutive 1s. What is the recurrence relation for a_n?
(A) a_n–2 + a_n–1 + 2^n–2
(B) a_n–2 + 2a_n–1 + 2^n–2
(C) 2a_n–2 + a_n–1 + 2^n–2
(D) 2a_n–2 + 2a_n–1 + 2^n–2

Answer: (A)

Explanation: