Let an be the number of n-bit strings that do NOT contain two consecut – McqOptions

MCQOPTIONS

1.	Let an be the number of n-bit strings that do NOT contain two consecutive 1s. Which one of the following is the recurrence relation for an?
A.	an = an – 1 + 2an - 2
B.	an = an – 1 + an - 2
C.	an = 2an – 1 + an - 2
D.	an = 2an – 1 + 2an - 2
Answer» C. an = 2an – 1 + an - 2

Discussion

No Comment Found

Related MCQs

Consider the following two sequences,X = {-1, 1, -1, 1, ...} andY = {1, \(\frac{1}{2}\), 3, \(\frac{1}{4}\),...}.Then:
How many 3 digit numbers can be formed using the numbers 6, 1, 2, 3 without repetition ?
If \({a_n} = \sum\limits_{r = 0}^n {\frac{1}{{{n_{{c_r}}}}}}\), then \(\sum\limits_{r = 0}^n {\frac{r}{{{n_{{c_r}}}}}}\) equals
If n pigeons are assigned to m pigeonholes then one of the pigeonholes must contain at least ______ pigeons.
Let an represents the number of bit strings of length n containing two consecutive 1s. What is the recurrence relation for an?
How many ways are there to pack six copies of the same book into four identical boxes, where a box can contain as many as six books ?
Given the recurrence relation f(n) = (n - 1) + f(n - 1), n > 72, f(2) = 1, then f(n) is:
Given below are two statements:Statement I: 5 divides n5 - n whenever n is a nonnegative integer.Statement II: 6 divides n3 - n whenever n is a nonnegative integer.In the light of the above statements. choose the correct answer from the options given below
Find the lexicographic ordering of the bit strings given below based on the ordering 0 < 1.(A) 001(B) 010(C) 011(D) 0001(E) 0101Choose the correct answer from the options given below:
Number of binary strings of length 5 that contain no two or more consecutive zeros, is: