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

GATE CSE 2024 Session 2 Q15: Growth of T(n) = 5T(n−1) − 6T(n−2) with T(0)=1, T(1)=2

Let $T(n)$ be the recurrence relation defined as follows:

$T(0) = 1, \quad T(1) = 2, \quad T(n) = 5T(n-1) - 6T(n-2) \ \text{ for } n \ge 2$

Which one of the following statements is TRUE?

Try it: multiple choice: exactly one correct option

Wrong answer costs 1/3 mark in GATE.

Show answer and explanation

Answer: A (official GATE 2024 final answer key)

Concept used: Linear homogeneous recurrence: the initial conditions fix the coefficients of each root's term.

First step: The characteristic equation $r^2 - 5r + 6 = 0$ has roots 2 and 3, so $T(n) = a2^n + b3^n$ ; solve for $a, b$ from $T(0), T(1)$ .

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

Source: official GATE 2024 Session 2 CS question paper and final answer key, organised by IISc Bangalore. Question paper · Answer key