Q2

MCQ1 mark, −0.33

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

Loading…