GATE CS 2024 Set 2 | Question 15
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 \ge 2\)
Which one of the following statements is TRUE?
Explanation
Answer: (A)
The characteristic equation is \(r^{2} - 5r + 6 = 0\), with roots 2 and 3, so \(T(n) = a \cdot 2^{n} + b \cdot 3^{n}\).
The initial values fix the constants: \(a + b = 1\) and \(2a + 3b = 2\), giving \(a = 1\) and \(b = 0\). Hence \(T(n) = 2^{n}\) exactly; for instance, \(T(2) = 5 \cdot 2 - 6 \cdot 1 = 4\).
These starting values make the \(3^{n}\) term vanish, so option C, which follows the larger root, is wrong here. Forms like \(n2^{n}\) and \(n3^{n}\) arise only from a repeated root.
Answer: A