Definition:Linearly Recurrent Sequence

Definition

A linearly recurrent sequence is a sequence which can be defined by a recurrence relation of the form:

$a_n = c_1 a_{n - 1} + c_2 a_{n - 2} + \cdots + c_m a_{n - m}$

with appropriate initial values for $a_1, a_2, \ldots, a_{n - 1}$.

Also known as

A linearly recurrent sequence can be referred to as a linear recurrence.

Sources

• 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.9$: Generating Functions