GATE CS 2016 Set 1 Q2 — Combinatorics: Counting, Recurrence Relations, Generating Functions

To find the recurrence relation for $a_n$, the number of $n$-bit strings that do not contain two consecutive $1$'s, we can analyze the possible endings of a valid $n$-bit string:

• Case 1: The string ends with $0$.
  If the last bit is $0$, the preceding $n-1$ bits can be any valid string of length $n-1$ that does not contain consecutive $1$'s. There are $a_{n-1}$ such strings.
• Case 2: The string ends with $1$.
  If the last bit is $1$, the second-to-last bit must be $0$ to avoid consecutive $1$'s (i.e., the string must end in $01$). The preceding $n-2$ bits can be any valid string of length $n-2$ that does not contain consecutive $1$'s. There are $a_{n-2}$ such strings.

Since these two cases are mutually exclusive and cover all valid $n$-bit strings, we sum them to get the total number of strings:

Verification with small values:

• For $n = 1$, the valid strings are $\{0, 1\}$, so $a_1 = 2$.
• For $n = 2$, the valid strings are $\{00, 01, 10\}$, so $a_2 = 3$.
• For $n = 3$, the valid strings are $\{000, 001, 010, 100, 101\}$, so $a_3 = 5$.

Using the recurrence relation: $a_3 = a_2 + a_1 = 3 + 2 = 5$, which matches our count.