Recurrence Relations MCQ Quiz - Objective Question with Answer for Recurrence Relations - Download Free PDF

The correct answer is : option 2.

Key Points

Explanation of the Recurrence Relation Solution

Given the recurrence relation: T(n) = T(2n/3) + 1

To solve this, we will use the Master Theorem for divide-and-conquer recurrences of the form:

T(n) = aT(n/b) + f(n)

In our case, a = 1, b = 3/2, and f(n) = 1.

Using the Master Theorem, we compare f(n) with n^log_b(a):

• a = 1
• b = 3/2
• log_b(a) = log(1) / log(3/2) = 0
• f(n) = 1

Since f(n) = 1 is Θ(1), it matches the case where f(n) = Θ(n^c) with c = 0. This corresponds to case 2 of the Master Theorem, where f(n) is polynomially smaller than n^log_b(a).

Therefore, the solution to the recurrence is:

T(n) = Θ(log n)

Thus, the correct answer is option 2.

Given:

Recurrence Relation:- bn = 2bn-1 + 1

Initial Condition b₁ = 7

Formula Used:

\(\frac{1 - x^{m + 1}}{1 - x} = 1 + x + x^2 + .... + x^m\)

Calculation:

We have.

⇒ b_n = 2b_{n - 1} + 1

⇒ b_{n - 1} = 2b_{n - 2} + 1

⇒ b_{n - 2} = 2b_{n - 3} + 1

⇒ b_{n - 3} = 2b_{n - 4} + 1

and so on.... b₁ = 7

Thus b_n = 2[2b_{n - 2} + 1] + 1

⇒ b_n = 2²b_{n - 2} + 2 + 1

⇒ b_n = 2²[2b_{n - 3} + 1] + 2 + 1

⇒ b_n = 2³b_{n - 3} + 2² + 2 + 1

⇒ b_n = 2⁴b_{n - 4} + 2³ + 2² + 2 + 1

⇒ b_n = 2^{n - 1}b₁ + [2^{n - 2} + 2^{n - 3} + ... + 2³ + 2² + 2 + 1]

⇒ b_n = 2^{n - 1}b₁ + \(\left( \frac{ 1 - 2^{n - 2 + 1}}{1 - 2} \right) \)

⇒ b_n = 2^{n - 1}b₁ + (2^{n - 1} - 1)

⇒ b_n = 2^{n - 1}(7) + (2^{n - 1} - 1)   [Putting b₁ = 7]

⇒ b_n = 2^{n - 1}(7 + 1) - 1

⇒ b_n = 2^{n - 1} (2³) - 1

⇒ b_n = 2^{n + 2} - 1

∴ The explicit formula for the given sequence is b_n = 2^{n + 2} - 1 

Solution:

Pn + 1 = aPn + b

given, a = 3 and b = -1

P_n+1 = 3P_n - 1 . . .(i) 

Put n=0 

P₁ = 3 P₀ - 1 = 6-1 = 5 

Put  n = 1 in equation (i) 

P₂ = 3P₂ - 1 = 15-1 = 14

Hence, P₂ is 14.

Although base condition is not mentioned for tower of Hanoi when number disc is 0, that is, n = 0

number of moves needed is 0.

T(0) = 0 (base condition for Tower of Hanoi)

T(1) = 2 × T(0) + 1 = 0 + 1 = 1

T(2) = 2 × T(1) + 1 = 2 + 1 = 3

T(3) = 2 × T(2) + 1 = 6 + 1 = 7

T(4) = 2 × T(3) + 1 = 14 + 1 = 15

T(5) = 2 × T(4) + 1 = 30 + 1 = 31

T(6) = 2 × T(5) + 1 = 62 + 1 = 63

T(7) = 2 × T(6) + 1 = 126 + 1 = 127

T(8) = 2 × T(7) + 1 = 254 + 1 = 255

Tips and Tricks:

Number of moves required for n disc in a Tower of Hanoi is 2n – 1 = 28 – 1 = 255.

We have to take n-bit strings that do not contain two consecutive 1’s

For n = 1, i.e. 1 bit string , number of strings with 1 bit = { 0, 1 } = 2

For n = 2 i.e. 2 bit string, number of strings with 2 bit = {00, 01, 10} = 3

For n = 3, i.e. 3 bit string, number of strings with 3 bit = {000, 001, 010, 100, 101} = 5

For n = 4 i.e. 4 bit string, number of strings with 4 bit = {0000, 0001, 0010, 0100, 1000, 0101, 1010, 1001} = 8

Here, these values are making a Fibonacci series. Because we are getting the next value by adding the previous two values like in Fibonacci sequence (0, 1, 1, 2, 3, 5, 8 ……..)

Recurrence relation for Fibonacci sequence is : T(n) = T (n -1 ) + T(n - 2)

We have to take n-bit strings that do not contain two consecutive 1’s

For n = 1, i.e. 1 bit string , number of strings with 1 bit = { 0, 1 } = 2

For n = 2 i.e. 2 bit string, number of strings with 2 bit = {00, 01, 10} = 3

For n = 3, i.e. 3 bit string, number of strings with 3 bit = {000, 001, 010, 100, 101} = 5

For n = 4 i.e. 4 bit string, number of strings with 4 bit = {0000, 0001, 0010, 0100, 1000, 0101, 1010, 1001} = 8

Here, these values are making a Fibonacci series. Because we are getting the next value by adding the previous two values like in Fibonacci sequence (0, 1, 1, 2, 3, 5, 8 ……..)

Recurrence relation for Fibonacci sequence is : T(n) = T (n -1 ) + T(n - 2)

The correct answer is : option 2.

Key Points

Explanation of the Recurrence Relation Solution

Given the recurrence relation: T(n) = T(2n/3) + 1

To solve this, we will use the Master Theorem for divide-and-conquer recurrences of the form:

T(n) = aT(n/b) + f(n)

In our case, a = 1, b = 3/2, and f(n) = 1.

Using the Master Theorem, we compare f(n) with n^log_b(a):

• a = 1
• b = 3/2
• log_b(a) = log(1) / log(3/2) = 0
• f(n) = 1

Since f(n) = 1 is Θ(1), it matches the case where f(n) = Θ(n^c) with c = 0. This corresponds to case 2 of the Master Theorem, where f(n) is polynomially smaller than n^log_b(a).

Therefore, the solution to the recurrence is:

T(n) = Θ(log n)

Thus, the correct answer is option 2.

Given:

Recurrence Relation:- bn = 2bn-1 + 1

Initial Condition b₁ = 7

Formula Used:

\(\frac{1 - x^{m + 1}}{1 - x} = 1 + x + x^2 + .... + x^m\)

Calculation:

We have.

⇒ b_n = 2b_{n - 1} + 1

⇒ b_{n - 1} = 2b_{n - 2} + 1

⇒ b_{n - 2} = 2b_{n - 3} + 1

⇒ b_{n - 3} = 2b_{n - 4} + 1

and so on.... b₁ = 7

Thus b_n = 2[2b_{n - 2} + 1] + 1

⇒ b_n = 2²b_{n - 2} + 2 + 1

⇒ b_n = 2²[2b_{n - 3} + 1] + 2 + 1

⇒ b_n = 2³b_{n - 3} + 2² + 2 + 1

⇒ b_n = 2⁴b_{n - 4} + 2³ + 2² + 2 + 1

⇒ b_n = 2^{n - 1}b₁ + [2^{n - 2} + 2^{n - 3} + ... + 2³ + 2² + 2 + 1]

⇒ b_n = 2^{n - 1}b₁ + \(\left( \frac{ 1 - 2^{n - 2 + 1}}{1 - 2} \right) \)

⇒ b_n = 2^{n - 1}b₁ + (2^{n - 1} - 1)

⇒ b_n = 2^{n - 1}(7) + (2^{n - 1} - 1)   [Putting b₁ = 7]

⇒ b_n = 2^{n - 1}(7 + 1) - 1

⇒ b_n = 2^{n - 1} (2³) - 1

⇒ b_n = 2^{n + 2} - 1

∴ The explicit formula for the given sequence is b_n = 2^{n + 2} - 1 

T(n)=2T(n−1)

T(n)= 2[2T(n−2)] = 2²T(n−2)

T(n)=2² [2T(n−3)]=2³T(n−3)

T(n)=2^kT(n−k)

n−k=0, n=k, T(0)=1

T(n)= O(2ⁿ)

Although base condition is not mentioned for tower of Hanoi when number disc is 0, that is, n = 0

number of moves needed is 0.

T(0) = 0 (base condition for Tower of Hanoi)

T(1) = 2 × T(0) + 1 = 0 + 1 = 1

T(2) = 2 × T(1) + 1 = 2 + 1 = 3

T(3) = 2 × T(2) + 1 = 6 + 1 = 7

T(4) = 2 × T(3) + 1 = 14 + 1 = 15

T(5) = 2 × T(4) + 1 = 30 + 1 = 31

T(6) = 2 × T(5) + 1 = 62 + 1 = 63

T(7) = 2 × T(6) + 1 = 126 + 1 = 127

T(8) = 2 × T(7) + 1 = 254 + 1 = 255

Tips and Tricks:

Number of moves required for n disc in a Tower of Hanoi is 2n – 1 = 28 – 1 = 255.

Solution:

Pn + 1 = aPn + b

given, a = 3 and b = -1

P_n+1 = 3P_n - 1 . . .(i) 

Put n=0 

P₁ = 3 P₀ - 1 = 6-1 = 5 

Put  n = 1 in equation (i) 

P₂ = 3P₂ - 1 = 15-1 = 14

Hence, P₂ is 14.

a₁ = a₀ + 1

a₂ = a₁ + 2

= a₀ + 1 + 2

a_n = a₀ + 1 + 2 + ……… + n

\(= 2 + \;\frac{{n\left( {n\; + \;1} \right)}}{2}\)

\({a_n} = \frac{{{n^2}\; + \;n\; + \;4}}{2}\)

We have to take n-bit strings that do not contain two consecutive 1’s

For n = 1, i.e. 1 bit string , number of strings with 1 bit = { 0, 1 } = 2

For n = 2 i.e. 2 bit string, number of strings with 2 bit = {00, 01, 10} = 3

For n = 3, i.e. 3 bit string, number of strings with 3 bit = {000, 001, 010, 100, 101} = 5

For n = 4 i.e. 4 bit string, number of strings with 4 bit = {0000, 0001, 0010, 0100, 1000, 0101, 1010, 1001} = 8

Here, these values are making a Fibonacci series. Because we are getting the next value by adding the previous two values like in Fibonacci sequence (0, 1, 1, 2, 3, 5, 8 ……..)

Recurrence relation for Fibonacci sequence is : T(n) = T (n -1 ) + T(n - 2)

Characteristic equation of recurrence relation a_n = 6a_n-2 - a_n-1 is

r² = 6 - r

r² + r - 6 = 0

(r - 2) (r + 3) = 0

∴ r = 2 or r = -3

The solution of recurrence relationa_n = 6 a_n-2 - a_n-1 is

α_n = α₁(2)ⁿ + α₂(-3)ⁿ

Using α₀ = 2

α₀ = α₁(2)⁰ + α₂(-3)⁰ = 2

∴ α₁ + α₂ = 2     ....(1)

Using α₁ = 9

α₁ = α₁(2)¹+ α₂(-3)¹ = 9

∴ 2α₁ - 3α₂ = 9    ....(2)

By solving (1) and (2)

α₁ = 3 and α₂ = - 1

T (n) = 10 T(n-1) – 25 T(n-2)

We can write it as :

T(n) – 10 T(n-1) + 25 T(n-2) = 0

Then in polynomial form, it can be represented as :

x² – 10x + 25 = 0

(x - 5)² = 0

Then the characteristic equation will be :

T(n ) = C₁5ⁿ + C₂.n.5ⁿ

T(0) = T(1) = 5

So, T(0) = C₁5⁰ + C₂.0.5⁰

5 = C₁

Now, T(1) = C₁ 5¹ + C₂1.5¹

5 = 5C₁+ 5C₂

i.e. C₁ + C₂ = 1

C₂ = -4

So, T(n) = 5.5ⁿ + (-4)n.5ⁿ