GATE CS 2015 Set 1 Q.59 (CS Q.49): Combinatorics, Counting, Recurrence Relations and Generating Functions

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_n = a_{n-1} + a_{n-2} + 2^{n-2}$

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

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

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

Official answer and solution

Solution

Derive the recurrence relation by partitioning bit strings of length n based on their ending bit patterns.

Let $a_n$ denote the number of bit strings of length $n$ containing two consecutive 1s.

We partition any valid string of length $n$ into mutually exclusive cases based on its suffix:

Ends in 0: The last bit is 0, so the first $n-1$ bits must contain two consecutive 1s. There are $a_{n-1}$ such strings.
Ends in 01: The last two bits are 01, so the first $n-2$ bits must contain two consecutive 1s. There are $a_{n-2}$ such strings.
Ends in 11: The last two bits are 11. Since this suffix already provides two consecutive 1s, the prefix of length $n-2$ can be ANY arbitrary bit string. The number of arbitrary bit strings of length $n-2$ is $2^{n-2}$ .

These three cases are mutually exclusive and collectively cover all valid bit strings of length $n$ .

Summing the counts gives the recurrence relation:

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

This matches option A.

Final answer

Common trap

Double-counting strings by adding 2^(n-2) to overlapping subcases.

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.