Let xn denote the number of binary strings of length n that contain no concecutives 0s.
Which of the following recurrences does xn satisfy
A
xn = 2xn−1
No worries! We‘ve got your back. Try BYJU‘S free classes today!
B
xn = x[n/2] + 1
No worries! We‘ve got your back. Try BYJU‘S free classes today!
C
xn = x[n/2] + n
No worries! We‘ve got your back. Try BYJU‘S free classes today!
D
xn = xn−1 + xn−2
Right on! Give the BNAT exam to get a 100% scholarship for BYJUS courses
Open in App
Solution
The correct option is Dxn = xn−1 + xn−2 The represents those strings with no consercutive 0's
Let, n = 1 x1 = 2
Let, n = 2 x2 = 3
Let, n =3 x3 = 5
Now, substituting n = 3 in all of the answers only choice (d) xn = xn−1 + xn−2 satisfies the number obtained from the tree counting.