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

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

Any valid $n$-bit binary string can either:

1. End in $0$: The first $n-1$ bits can be any valid $(n-1)$-bit string without consecutive $1$s. There are $a_{n-1}$ such strings.

2. End in $1$: The bit immediately preceding it must be $0$ (so it ends in $01$) to prevent consecutive $1$s. The remaining first $n-2$ bits can be any valid $(n-2)$-bit string. There are $a_{n-2}$ such strings.

Summing these two mutually exclusive cases gives:

Hence, option (B) is the correct recurrence relation.