## 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?
 A xn = 2xn-1 B xn = x⌊n/2⌋+1 C xn = x⌊n/2⌋+n D xn = xn-1+xn-2
Algorithms        Recurrence       Gate-2008
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.
 Question 2
Let xn denote the number of binary strings of length n that contain no consecutive 0s. The value of x5 is
 A 5 B 7 C 8 D 16
Algorithms        Recurrence       Gate-2008
Question 2 Explanation:
From above question we have found that equation,
xn = xn-1 + xn-2
satisfies.
And also we have found the value of x4 and x3 for the above equation.
So, according to the equation the value of x5 will be,
x5 = x3 + x4
= 5 + 8
= 13
Hence , none of the given option is correct.
 Question 3

 A 2n+1 – n – 2 B 2n – n C 2n+1 – 2n – 2 D 2n + n
Algorithms        Recurrence       Gate-2004
Question 3 Explanation:
T(1) =1
T(n) = 2T(n-1) + n
T(2) = 2T(1) + 2 = 2 + 2 = 4
T(3) = 2T(2) + n = 2(4) + 3 = 11
T(4) = 2T(3) + 4 = 22 + 4 = 26
Let check with the options:
Option A:
n=4
24+1 - 4 - 2
32 - 6
26 (✔️)
Option B:
n=4
2n-n
24-4
12(✖️)
Option C:
n=4
24+1 - 2(4) - 8
32 - 10
22(✖️)
Option D:
n=4
2n - n
24 - 4
12(✖️)
 Question 4
Consider the following recurrence relation
 A B C D
Algorithms        Recurrence       Gate-2003
Question 4 Explanation:

Considering floor value for square root of numbers.
Successive root number of numbers are in the series 3, 5, 7, ... like 3 numbers from 1... 4, 5 numbers 5-9 and so on.
 Question 5
The solution to the recurrence equation T(2k) = 3T(2k-1) + 1, T(1) = 1 is
 A B C D
Algorithms        Recurrence       Gate-2002
Question 5 Explanation:
T(2k)=3T(2k-1)+1
T(1)=1
k=0; T(1)=3T(2-1)+1
k=1; T(2)=3T(20)+1=3(1)+1=4
k=2; T(4)=3T(21)+1=3(4)+1=13
k=3; T(8)=3T(22)+1=3(13)+1=40
k=4; T(16)=3T(23)+1=3(40)+1=121
Simply go through the options.
Option B:
k=4 ⇒ (34+1-1)/2
⇒ (243-1)/2
⇒ 121
There are 5 questions to complete.