Recurrences

Finding linear recurrences

Recurrence Calculator

Type the first terms of the sequence separated by commas in the box below and press <Enter>

Theory

We assume that a number sequence obeys a linear recurrence relation, i.e. the term $f(n), n \ge k$, can be computed recursively from $k$ previous terms: $$ f(n) = a_1 f(n-1) + a_2 f(n-2) + ... + a_k f(n-k) + c_1 n + c_0 \tag {1} $$ $k$ is called the order of the recurrence.

This recurrence can be iteratively evaluated if we know the $k$ initial conditions $f(0), f(1), ..., f(k-1)$ and the $k + 2$ coefficients $a_1, a_2, ...a_k, c_1, c_0$ . Now, suppose that we know the first $N$ values $f(0), f(1), ... f(N-1)$ and want to find out the coefficients such that Eq. (1) is satisfied for all these values.

The first $k$ values are initial conditions and cannot be used as equations. The needed number of equations $N - k$ must exceed the number $k + 2$ of unknows: $$ N - k \ge k + 2 $$ It follows that the possible recurrence order must satisfy: $$ k \lt \lfloor N / 2 \rfloor \tag {2} $$

We designate the coefficients by $x_i$ to indicate "unknowns" and write Eq. (1) as: $$ f(n) = f(n-1) x_0 + f(n-2) x_1 + ... + f(n-k) x_{k - 1} + n x_k + 1 x_{k+1} \tag {3} $$ We introduce the "row" vector $$ {\pmb F} (n, k) = (f(n-1), f(n-2), ... f(n-k), n, 1) \tag {4} $$ and the "column" vector $$ {\pmb x} = (x_0, x_1, ... x_{k - 1} , x_k, x_{k+1}) \tag {5} $$ Both vectors have $k + 2$ components. The determining $N - k$ equations can be written as scalar products: $$\begin{align} {\pmb F} (k, k) \cdot {\pmb x} & = f(k) \tag {6} \\ {\pmb F} (k+1, k) \cdot {\pmb x} & = f(k+1) \\ ... \\ {\pmb F} (N-1, k) \cdot {\pmb x} & = f(N-1) \end{align}$$ or in matrix notation: $$ \begin{equation} \begin{bmatrix} {\pmb F} (k, k) \tag {7} \\ {\pmb F} (k+1, k) \\ ... \\ {\pmb F} (N-1, k) \end{bmatrix} \cdot \begin{bmatrix} x_0 \\ x_1 \\ ... \\ x_{k+1} \end{bmatrix} = \begin{bmatrix} f(k) \\ f(k+1) \\ ... \\ f(N-1) \end{bmatrix} \end{equation} $$

We start with $k = 0$, set up the matrix equation and try to solve it. If we find a solution we are done. If the system has no solution we increase $k$ by 1 and try again. In this way we proceed until we find a solution or reach the highest $k$ given by Eq. (2).

Finding linear recurrences

Recurrence Calculator

Theory

Links