A recurrence relation or a difference equation is the discrete analog to differential equations.

Definition: First Order Difference Equation

A first order difference equation is a recursively defined sequence in the form

What makes this first order is that we only need to know the most recent previous value to find the next value. It also has clear parallel to the first-order ODEs.

Definition: K-th Order Difference Equation

A difference equation of order () has the form of

Examples

Example

Sometimes we use a different notation:

Example: Pascal's rule

See: Pascal’s rule

The binomial coefficient can be described by the following recurrence relation

Linear Difference Equation

In a linear difference equation, the th term is equated to a linear function of previous terms. A famous example is the Fibonacci numbers:

with initial conditions and . This is a second-order linear homogeneous difference equation.

Modeling Discrete Systems

Difference equations are great ways to model discrete systems as they are mathematically concise and precise, and they are also convenient for step-by-step analysis. However, deriving a closed-form solution from difference equations is often challenging, and sometimes a more imperative description like the block diagram may be more preferable to describe a system.