42 votes 42 votes 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? $x_n = 2x_{n-1}$ $x_n = x_{\lfloor n/2 \rfloor} + 1$ $x_n = x_{\lfloor n/2 \rfloor} + n$ $x_n = x_{n-1} + x_{n-2}$ Algorithms gatecse-2008 algorithms recurrence-relation normal + – Kathleen asked Sep 12, 2014 • edited Jun 20, 2021 by Lakshman Bhaiya Kathleen 8.6k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply Chhotu commented Aug 26, 2017 reply Follow Share Please refer --> http://www.geeksforgeeks.org/count-number-binary-strings-without-consecutive-1s/ 1 votes 1 votes Nirmal Gaur commented Jan 13, 2018 reply Follow Share Similar problem: https://gateoverflow.in/39636/gate-2016-1-2 4 votes 4 votes Deepak Poonia commented Jun 19, 2022 reply Follow Share $\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 2 votes 2 votes Please log in or register to add a comment.
0 votes 0 votes 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 rishav1995 answered Sep 6, 2019 rishav1995 comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes D is the correct answer. eshita1997 answered Jan 14, 2021 eshita1997 comment Share Follow See all 0 reply Please log in or register to add a comment.