Recurrence
Question 1 |
Let xn denote the number of binary strings of length n that contain no consecutive 0s.
Which of the following recurrences does xn satisfy?
xn = 2xn-1
| |
xn = x⌊n/2⌋+1 | |
xn = x⌊n/2⌋+n | |
xn = xn-1+xn-2
|
Question 1 Explanation:
xn = number of binary strings of length n that contains non-consecutive 0’s.
⇒ Let us consider n=1
Possible binary strings: 0, 1
So, x1 = 2
⇒ For n = 2;
Possible strings are,
010
110
111
011
101
So, x3 = 5
⇒ For n=4,
Possible strings are
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
0 1 1 0
0 1 0 1
1 0 1 0
1 1 1 1
So,
x4=8,
Hence, for all values of x4 above only option (D) satisfies.
⇒ Let us consider n=1
Possible binary strings: 0, 1
So, x1 = 2
⇒ For n = 2;
Possible strings are,
010
110
111
011
101
So, x3 = 5
⇒ For n=4,
Possible strings are
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
0 1 1 0
0 1 0 1
1 0 1 0
1 1 1 1
So,
x4=8,
Hence, for all values of x4 above only option (D) satisfies.
There is 1 question to complete.