Exams › GATE › Engineering Mathematics

Let T(n) be the recurrence relation defined as follows: T(0) = 1, T(1) = 2, and T(n) = 5T(n − 1) − 6T(n − 2) for n ≥ 2 Which one of the following statements is TRUE?

1. T(n) = Θ(2ⁿ)
2. T(n) = Θ(n2ⁿ)
3. T(n) = Θ(3ⁿ)
4. T(n) = Θ(n3ⁿ)

Correct answer: T(n) = Θ(3ⁿ)

Solution

The recurrence relation T(n) = 5T(n − 1) − 6T(n − 2) has a characteristic polynomial with roots that indicate exponential growth, specifically leading to a solution of the form T(n) = Θ(3ⁿ), which aligns with the dominant root of the characteristic equation.

Related GATE Engineering Mathematics questions

• The second-order differential equation in an unknown function u: u(x,y) is defined as ∂²u/∂x² = 2. Assuming g: g(x), f: f(y), and h: h(y), the general solution of the above differential equation is
• Which of the following equations belong/belongs to the class of second-order, linear, homogeneous partial differential equations:
• The solution of the equation x dy/dx + y = 0 passing through the point (1,1) is
• The Laplace transform F(s) of the exponential function, f(t)=e^(at) when t≥0, where a is a constant and (s−a)>0, is
• The Laplace transform of sinh(at) is
• An ordinary differential equation is given below. (dy/dx)(x ln x) = y The solution for the above equation is (Note: K denotes a constant in the options)

⚔️ Practice GATE Engineering Mathematics free + battle 1v1 →