GATE CSE 2008 | Question: 78

Question

Let $x_n$ denote the number of binary strings of length $n$ that contain no consecutive $0$s.

Which of the following recurrences does $x_n$ satisfy?

• A. $x_n = 2x_{n-1}$
• B. $x_n = x_{\lfloor n/2 \rfloor} + 1$
• C. $x_n = x_{\lfloor n/2 \rfloor} + n$
• D. $x_n = x_{n-1} + x_{n-2}$

Comments

Please refer --> http://www.geeksforgeeks.org/count-number-binary-strings-without-consecutive-1s/

---

Similar problem:

https://gateoverflow.in/39636/gate-2016-1-2

---

$\color{red}{\text{Detailed Video Solution of this GATE question}}$(Click Below):

Detailed Video Solution

$\color{red}{\text{Complete Recurrence Relation Playlist}}$(Click Below):

Complete Recurrence Relations Playlist 

Answer 1

x1 = 0, 1  [Total = 1 (since 0 is not considered)]

x2 = 10,11 [Total = 2]

x3 = 100,101,110,111 [Total = 3]

x4 = 1000,1001,1010,1011,1100,1101,1110,1111 [Total = 5]

Applying for x4 we get that option D satisfies it -

x4 = x3+x2

     = 3+2 = 5

Answer 2

D is the correct answer.