Recurrence
Question 1 
Let x_{n} denote the number of binary strings of length n that contain no consecutive 0s.
Which of the following recurrences does x_{n} satisfy?
x_{n} = 2x_{n1}
 
x_{n} = x_{⌊n/2⌋}+1
 
x_{n} = x_{⌊n/2⌋}+n
 
x_{n} = x_{n1}+x_{n2}

Question 1 Explanation:
x_{n} = number of binary strings of length n that contains nonconsecutive 0’s.
⇒ Let us consider n=1
Possible binary strings: 0, 1
So, x_{1} = 2
⇒ For n = 2;
Possible strings are,
010
110
111
011
101
So, x_{3} = 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,
x_{4}=8,
Hence, for all values of x_{4} above only option (D) satisfies.
⇒ Let us consider n=1
Possible binary strings: 0, 1
So, x_{1} = 2
⇒ For n = 2;
Possible strings are,
010
110
111
011
101
So, x_{3} = 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,
x_{4}=8,
Hence, for all values of x_{4} above only option (D) satisfies.
Question 2 
Let x_{n} denote the number of binary strings of length n that contain no consecutive 0s.
The value of x_{5} is
5  
7  
8  
16 
Question 2 Explanation:
From above question we have found that equation,
x_{n} = x_{n1} + x_{n2}
satisfies.
And also we have found the value of x_{4} and x_{3} for the above equation.
So, according to the equation the value of x_{5} will be,
x_{5} = x_{3} + x_{4}
= 5 + 8
= 13
Hence , none of the given option is correct.
x_{n} = x_{n1} + x_{n2}
satisfies.
And also we have found the value of x_{4} and x_{3} for the above equation.
So, according to the equation the value of x_{5} will be,
x_{5} = x_{3} + x_{4}
= 5 + 8
= 13
Hence , none of the given option is correct.
Question 3 
2^{n+1} – n – 2  
2^{n} – n
 
2^{n+1} – 2n – 2  
2^{n} + n

Question 3 Explanation:
T(1) =1
T(n) = 2T(n1) + 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
2^{4+1}  4  2
32  6
26 (✔️)
Option B:
n=4
2^{n}n
2^{4}4
12(✖️)
Option C:
n=4
2^{4+1}  2(4)  8
32  10
22(✖️)
Option D:
n=4
2^{n}  n
2^{4}  4
12(✖️)
T(n) = 2T(n1) + 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
2^{4+1}  4  2
32  6
26 (✔️)
Option B:
n=4
2^{n}n
2^{4}4
12(✖️)
Option C:
n=4
2^{4+1}  2(4)  8
32  10
22(✖️)
Option D:
n=4
2^{n}  n
2^{4}  4
12(✖️)
Question 4 
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 59 and so on.
Question 5 
The solution to the recurrence equation T(2^{k}) = 3T(2^{k1}) + 1, T(1) = 1 is
Question 5 Explanation:
T(2^{k})=3T(2^{k1})+1
T(1)=1
k=0; T(1)=3T(2^{1})+1
k=1; T(2)=3T(2^{0})+1=3(1)+1=4
k=2; T(4)=3T(2^{1})+1=3(4)+1=13
k=3; T(8)=3T(2^{2})+1=3(13)+1=40
k=4; T(16)=3T(2^{3})+1=3(40)+1=121
Simply go through the options.
Option B:
k=4 ⇒ (3^{4+1}1)/2
⇒ (2431)/2
⇒ 121
T(1)=1
k=0; T(1)=3T(2^{1})+1
k=1; T(2)=3T(2^{0})+1=3(1)+1=4
k=2; T(4)=3T(2^{1})+1=3(4)+1=13
k=3; T(8)=3T(2^{2})+1=3(13)+1=40
k=4; T(16)=3T(2^{3})+1=3(40)+1=121
Simply go through the options.
Option B:
k=4 ⇒ (3^{4+1}1)/2
⇒ (2431)/2
⇒ 121
There are 5 questions to complete.