Definition:Recursive Sequence/Recurrence Relation

From ProofWiki
Jump to navigation Jump to search

Definition

The equation which defines a recursive sequence is called a recurrence relation or difference equation.


Examples

Fibonacci Sequence

The classic example of a recursive sequence is the Fibonacci sequence:

$F_n = F_{n - 1} + F_{n - 2}$

such that $F_1 = F_2 = 1$.


Also known as

A recurrence relation is also known as a recursive relation.

A recurrence relation can also be seen referred to as a difference equation, and vice versa.

However, a difference equation is in fact a particular type of recurrence relation, and the two are not strictly synonymous.


Also see

  • Results about recurrence relations can be found here.


Sources