Library/Algebra/Sequences/Recurrence relations/Linear recurrence relations

Linear recurrence relations

Overview
Important

A linear recurrence relation is a rule that defines each term of a sequence as a linear combination of previous terms. The most common type is the linear recurrence of order kk, where each term depends on the previous kk terms. For example, the Fibonacci sequence is defined by Fn=Fn−1+Fn−2F_n = F_{n-1} + F_{n-2}.

Important properties

  • The coefficients in the relation are constants.

  • Initial terms (starting values) are needed to generate the sequence.

  • Homogeneous linear recurrences have all terms on one side and zero on the other (e.g., an=2an−1+3an−2a_n = 2a_{n-1} + 3a_{n-2}).

  • Non-homogeneous linear recurrences include an extra function or constant (e.g., an=2an−1+1a_n = 2a_{n-1} + 1).