A recurrence relation is an equation that defines the $n^{th}$ term of a number sequence as a function of some of its previous terms. It has the general form $$ A(n) = c_1 A(n - 1) + c_2 A(n - 2) + \cdots + c_k A(n - k) $$ for some natural number $k$ and constant coefficients $c_1, c_2, \dots, c_k \in \mathbb{R}$, ($c_k \ne 0$), where $k$ is known as the order of the relation. A $k$-order recurrence relation depends on the $k$ previous terms. First order recurrences have the form $x_k = c \cdot x_{k-1}$. When $k > 1$, we say that the relation is a higher order recurrence relation.
An infinite sequence $\langle x_0, x_1, x_2, \dots \rangle$ satisfying a $k$-order recurrence relation is then uniquely determined by its first $k$ terms. For example; the Fibonnaci sequence $$ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \ldots $$ is characterized by the second order relation $$ F_n = F_{n-1} + F_{n-2} $$ and the inital values $$ F_0 = 0 \\ F_1 = 1. $$
The type of recurrence relations we consider here have some common properties:
The expression $A(n)$ is linear in the sense that we can view it as a polynomial of degree one in $k$ variables: $$ x_n = c_1 x_{n - 1} + c_2 x_{n - 2} + \cdots + c_k x_{n - k}. $$ The exponent of each $x_{i \in [n-k .. n-1]}$ is one.
The coefficients $c_1, c_2, \ldots, c_k$ do not depend on $n$.