GATE CS 2016 Set 1 Q.12 (CS Q.2): Combinatorics, Counting, Recurrence Relations and Generating Functions

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

$a_n = a_{n-1} + 2a_{n-2}$

$a_n = a_{n-1} + a_{n-2}$

$a_n = 2a_{n-1} + a_{n-2}$

$a_n = 2a_{n-1} + 2a_{n-2}$

Official answer and solution

Solution

Classify $n$ -bit valid strings by their last bit to set up the linear recurrence relation.

Let $a_n$ denote the number of $n$ -bit binary strings with no consecutive 1s.

Consider the final bit of any valid $n$ -bit string:

If the string ends in 0, removing the final 0 leaves a valid $(n-1)$ -bit string with no consecutive 1s. There are $a_{n-1}$ such strings.
If the string ends in 1, the preceding bit must be 0 (since consecutive 1s are forbidden). Thus the string must end in the suffix '01'. Removing this suffix leaves a valid $(n-2)$ -bit string with no consecutive 1s. There are $a_{n-2}$ such strings.

Since every valid string either ends in 0 or ends in 01, by the rule of sum:

a_n = a_{n-1} + a_{n-2}

Final answer

Common trap

Multiplying $a_{n-2}$ by 2, which would erroneously allow the preceding bit to be 1.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.