GATE CS 2015 Q46: Recurrence Relation for Bit Strings w/ Consecutive 1s

```

Computer Sciences > GATE 2015 SET-1 > Recurrence Relations

Let a_n represent the number of bit strings of length n containing two consecutive 1s. What is the recurrence relation for a_n?

A

a_n-2 + a_n-1 + 2^n-2

B

a_n-2 + 2a_n-1 + 2^n-2

C

2a_n-2 + a_n-1 + 2^n-2

D

2a_n-2 + 2a_n-1 + 2^n-2

Correct : a

Similar Questions

Consider the following recurrence relation: Which one of the following options is CORRECT?

#878 MCQ

Let T(n) be the recurrence relation defined as follows: T(0) = 1, T(1) = 2, and T(n) = 5T(n-1) - 6T(n-2) for n ≥ 2 Which one of the following statements is TRUE...

#903 MCQ

Consider the following recurrence relation:T(n)=2T(n-1)+n2n for n>0, T(0)=1.Which ONE of the following options is CORRECT?

#1363 MCQ

Related Topics

No tags found

Unique Visitor Count

Total Unique Visitors

Loading......