Question

Let $a_n$ be the number of n-bit strings that do NOT contain two consecutive 1's. Which one of the following is the recurrence relation for $a_n$ ?

• A. $a_n$ = $a_{n-1}$ + $2a_{n-2}$
• B. $a_n$ = $a_{n-1}$ + $a_{n-2}$
• C. $a_n$ = $2a_{n-1}$ + $a_{n-2}$
• D. $a_n$ = $2a_{n-1}$ + $2a_{n-2}$

Answer 1

The correct option is B $a_n$ = $a_{n-1}$ + $a_{n-2}$

Let $a_n$ be the number of n-bit strings that do not contain two consecutive 1's. we wish to develop a recurrence relation for $a_n$. Consider 1 bit strings 0, 1
So, $a_1$ = 2
Consider 2 bit strings 00, 01, 10, 11
Out of minimum only 00, 01, 10 do not contain two consecutive 1's.
So, $a_2$ = 3

Out of minimum six strings only 000, 001, 010, 100 and 101 five strings satisfy do not contain two consercutive 1's.
So, $a_3$ = 5. Three numbers $a_1$, $a_2$, $a_3$ satisfy clearly only (b) $a_n$ = $a_{n-1}$ + $a_{n-2}$ is correct