Recurrence Relations

Once we model a problem with a recurrence, we need to solve it to find a closed-form expression for $a_{n}$ .

Linear Homogeneous Recurrences

Form:

c_{k} a_{n + k} + \dots + c_{1} a_{n + 1} + c_{0} a_{n} = 0

c_{k} r^{k} + \dots + c_{1} r + c_{0} = 0

Distinct Roots: $a_{n} = A r_{1}^{n} + B r_{2}^{n} + \dots$
Repeated Roots (multiplicity $m$ ): Include terms $n r^{n}, n^{2} r^{n}$ , etc.

Example: If $(r - 2)^{2} = 0$ , then $a_{n} = A \cdot 2^{n} + B \cdot n \cdot 2^{n}$ .

Example (Fibonacci)

F_{n} = F_{n - 1} + F_{n - 2} ⟹ r^{2} - r - 1 = 0

. Roots:

ϕ = \frac{1 + 5}{2}, ψ = \frac{1 - 5}{2}

F_{n} = A ϕ^{n} + B ψ^{n}

. Using

F_{0} = 0, F_{1} = 1

, we solve for

A, B

to get Binet's Formula.

Form:

a_{n} + c_{1} a_{n - 1} = f (n)

. Solution = (Homogeneous Solution) + (Particular Solution).

Guess particular solution based on $f (n)$ (e.g., if $f (n)$ is linear, guess $A n + B$ ).

Exercise (Problem 1)

Solve the recurrence

a_{n} = 5 a_{n - 1} - 6 a_{n - 2}

with

a_{0} = 1, a_{1} = 4

Exercise (Problem 2)

Solve

a_{n} = 2 a_{n - 1} + 1

with

a_{0} = 0

Exercise (Problem 3)

Find the general solution for

a_{n} - 4 a_{n - 1} + 4 a_{n - 2} = 0