The GATE Grind

GATE 2016 CS – Question 12

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

Let $a_n$ 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$?

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

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) $a_n = a_{n-1} + a_{n-2}$

Explanation

Split the valid strings by their last bit. If it is 0, the first $n-1$ bits can be any valid string, giving $a_{n-1}$ strings. If it is 1, the bit before it must be 0, and the first $n-2$ bits can be any valid string, giving $a_{n-2}$ strings. So $a_n = a_{n-1} + a_{n-2}$.