Let u0, u1, u2,…, un,… be a sequence. If the terms satisfy the first‐order difference equation un + 1 + aun = 0, it is easy to see that un = A(−a)n, where A( = u0) is arbitrary.
Suppose that the terms satisfy the second‐order difference equation un + 2 + aun + 1 + bun = 0. Let α and β be the roots of the quadratic ‘auxiliary equation’ x2 + ax + b = 0. If α ≠ β, then un = Aαn + Bβn, and if α = β ≠ 0, then un = (A + Bn)αn, where A and B are arbitrary constants. For example, the Fibonacci sequence is given by the difference equation un + 2 = un + 1 + un, with u0 = 1 and u1 = 1, and the above method gives Binet’s formula
The above theory generalizes to linear constant coefficient difference equations (see linear equation) of higher orders, with the solutions forming a vector space with dimension equalling the order. The solutions to an inhomogeneous linear difference equation are a particular solution added to the homogeneous solutions. Difference equations, also called recurrence relations, do not necessarily have constant coefficients like those considered above. Such difference equations may be approached using generating functions.