Library/Algebra/Sequences/Recurrence relations/Recurrence relations (other)

Recurrence relations (other)

Overview
Important

Not all recurrence relations are simple or linear. Some sequences are defined by more complicated rules, such as involving more than two previous terms, having variable coefficients, or being non-linear. These are called 'other' or 'general' recurrence relations.

Important properties

  • A recurrence relation can involve any number of previous terms (e.g., an=an−1+an−2+an−3a_n = a_{n-1} + a_{n-2} + a_{n-3}).

  • Coefficients in the relation can depend on nn (e.g., an=nan−1a_n = n a_{n-1}).

  • Some recurrence relations are non-linear (e.g., an=an−12−an−2a_n = a_{n-1}^2 - a_{n-2}).

  • Solving these relations often requires creative approaches, such as guessing, substitution, or using generating functions.