Let $T(n)$ be the recurrence relation defined as follows: $$T(0) = 1,$$ $$T(1) = 2, \text{ and}$$ $$T(n) = 5T(n - 1) - 6T(n - 2) \quad \text{for } n \ge 2$$ Which one of the following statements is TRUE?

To solve the linear homogeneous recurrence relation with constant coefficients:

The characteristic equation is:

The general solution is:

Using the given initial conditions:

• For $n = 0$: $T(0) = c_1 + c_2 = 1$

• For $n = 1$: $T(1) = 2c_1 + 3c_2 = 2$

Multiplying the first equation by $2$ and subtracting from the second:

Substituting $c_2 = 0$ into $c_1 + c_2 = 1$ gives $c_1 = 1$.

Therefore, the closed-form solution is:

Hence, $T(n) = \Theta(2^n)$, which corresponds to (A).