Recurrence Relation
Summary:
The solution to the first order recurrence relation un = aun-1 + b is
un = an-1 u1 + b(an-1 - 1) / (a - 1), where a ≠ 1.
If a = 1, then un = u1 + (n - 1)b.
For the second order recurrence relation un = aun-1 + bun-2 ,
we first solve the characteristic equation m2 - am - b = 0.
If the roots m1, m2 are real and distinct, then the solution is un = Am1n + Bm2n
If the roots m1 = m2 = m are equal, then the solution is un = (A + Bn)mn.
If the roots r(cos θ ± i sin θ) are complex, then the solution is un = rn (A cos nθ + B sin nθ)