Question

If \( U_{n+1} = 3U_n - 2U_{n-1} \) and \( U_0 = 2, U_1 = 3 \), then \( U_n \) is equal to

• A. \( 1 - 2^n \)
• B. \( 2^n + 1 \)
• C. \( 2^n - 1 \)
• D. \( 2^n + 2 \)

Hint:

For linear recurrence relations, try solving using characteristic equations to find the general form.

Answer 1

The Correct Option is B

We are given the recurrence relation: \( U_{n+1} = 3U_n - 2U_{n-1} \), with \( U_0 = 2 \), \( U_1 = 3 \)
Let us try to solve this recurrence by assuming a solution of the form \( U_n = A \cdot r^n \)
Step 1: Characteristic Equation
Substitute into recurrence:
\( r^{n+1} = 3r^n - 2r^{n-1} \Rightarrow r^2 = 3r - 2 \Rightarrow r^2 - 3r + 2 = 0 \)
Solving this: \( r = 1, 2 \)
Step 2: General Solution
The general solution is: \( U_n = A(1)^n + B(2)^n = A + B \cdot 2^n \)
Step 3: Use Initial Conditions
\( U_0 = A + B = 2 \quad \text{(i)} \)
\( U_1 = A + 2B = 3 \quad \text{(ii)} \)
Subtract (i) from (ii):
\( (A + 2B) - (A + B) = 3 - 2 \Rightarrow B = 1 \)
Substitute in (i): \( A + 1 = 2 \Rightarrow A = 1 \)
Final Solution:
\( U_n = 1 + 2^n = 2^n + 1 \)