The GATE Grind

GATE 2015 CS – Question 45

Engineering Mathematics · Discrete Mathematics: Combinatorics (Counting, Recurrence Relations, Generating Functions) · 2 marks · Multiple choice

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

  1. $a_{n-2} + a_{n-1} + 2^{n-2}$
  2. $a_{n-2} + 2a_{n-1} + 2^{n-2}$
  3. $2a_{n-2} + a_{n-1} + 2^{n-2}$
  4. $2a_{n-2} + 2a_{n-1} + 2^{n-2}$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) $a_{n-2} + a_{n-1} + 2^{n-2}$

Explanation

Split the strings by how they end. If a string ends in 0, the first $n-1$ bits must already contain two consecutive 1s, which gives $a_{n-1}$ strings. If it ends in 01, the first $n-2$ bits must contain them, which gives $a_{n-2}$. If it ends in 11, the first $n-2$ bits can be anything, which gives $2^{n-2}$. So $a_n = a_{n-1} + a_{n-2} + 2^{n-2}$.