Solve the recurrence relation aₙ = 3aₙ₋₁ - 2aₙ₋₂ with initial conditions

Question

Solve the recurrence relation $a_n = 3a_{n-1} - 2a_{n-2}$ with initial conditions $a_0 = 1$ and $a_1 = 3$ .

(JEE Advanced 2021, similar pattern)

Solution — Step by Step

For a linear recurrence $a_n = c_1 a_{n-1} + c_2 a_{n-2}$ , assume $a_n = r^n$ and substitute:

r^n = 3r^{n-1} - 2r^{n-2}

Divide by $r^{n-2}$ :

r^2 = 3r - 2

r^2 - 3r + 2 = 0

r^2 - 3r + 2 = (r - 1)(r - 2) = 0

Roots: $r_1 = 1$ and $r_2 = 2$ .

Since the roots are distinct, the general solution is:

a_n = A \cdot 1^n + B \cdot 2^n = A + B \cdot 2^n

From $a_0 = 1$ : $A + B \cdot 2^0 = 1 \implies A + B = 1$

From $a_1 = 3$ : $A + B \cdot 2^1 = 3 \implies A + 2B = 3$

Subtract: $B = 2$ , so $A = -1$ .

\boxed{a_n = 2^{n+1} - 1}

Verification: $a_0 = 2 - 1 = 1$ ✓, $a_1 = 4 - 1 = 3$ ✓, $a_2 = 8 - 1 = 7$ . Check: $3(3) - 2(1) = 7$ ✓.

Why This Works

The substitution $a_n = r^n$ works because the recurrence is linear with constant coefficients — each term is a fixed linear combination of previous terms. Exponentials are the “eigenfunctions” of such recurrences, just as they are for linear differential equations.

When the characteristic equation has distinct roots $r_1$ and $r_2$ , both $r_1^n$ and $r_2^n$ satisfy the recurrence, and any linear combination $Ar_1^n + Br_2^n$ also satisfies it. The two initial conditions pin down the specific values of $A$ and $B$ .

If the roots were equal (repeated root $r$ ), the general solution would be $a_n = (A + Bn)r^n$ instead — the $n$ factor appears because we need two linearly independent solutions.

Alternative Method — Generating the sequence and spotting the pattern

Compute a few terms: $a_0 = 1, a_1 = 3, a_2 = 7, a_3 = 15, a_4 = 31$ .

These are $2^1 - 1, 2^2 - 1, 2^3 - 1, 2^4 - 1, 2^5 - 1$ . The pattern $a_n = 2^{n+1} - 1$ is clear.

For JEE, if the characteristic equation has nice integer roots, you can often spot the closed form by computing 4-5 terms and looking for a pattern. But the characteristic equation method is the rigorous approach — use it for the proof, and the pattern-spotting to verify. JEE Advanced sometimes gives recurrences where the pattern isn’t obvious, so the systematic method is essential.

Common Mistake

Students sometimes write the characteristic equation incorrectly. For $a_n = 3a_{n-1} - 2a_{n-2}$ , the equation is $r^2 - 3r + 2 = 0$ (move everything to one side). A common error is writing $r^2 + 3r - 2 = 0$ — getting the signs wrong. Always rearrange as $a_n - 3a_{n-1} + 2a_{n-2} = 0$ , then replace $a_n \to r^2, a_{n-1} \to r, a_{n-2} \to 1$ .

Question

Solution — Step by Step

Why This Works

Alternative Method — Generating the sequence and spotting the pattern

Common Mistake

Try These Next