# linear recurrence

A sequence $x_{0},x_{1},\ldots,$ is said to satisfy a general linear recurrence if there are constants $a_{n,i}$ and $f_{n}$ such that

 $x_{n}=\sum_{i=1}^{n}a_{n,i}x_{n-i}+f_{n}$

The sequence $\{f_{n}\}$ is called the non-homogeneous part of the recurrence.

If $f_{n}=0$ for all $n$ then the recurrence is said to be homogeneous.

In this case if $x$ and $x^{\prime}$ are two solutions to the recurrence, and $A$ and $B$ are constants, then $Ax+Bx^{\prime}$ are also solutions.

If $a_{n,i}=a_{i}$ for all $i$ then the recurrence is called a linear recurrence with constant coefficients. Such a recurrence with $a_{n,i}=0$ for all $i>k$ and $a_{k}\neq 0$ is said to be of finite order and the smallest such integer $k$ is called the order of the recurrence. If no such $k$ exists, the recurrence is said to be of infinite order.

For example, the Fibonacci sequence is a linear recurrence with constant coefficients and order 2.

Now suppose that $x=\{x_{n}\}$ satisfies a homogeneous linear recurrence of finite order $k$. The polynomial $F_{x}=u^{k}-a_{1}u^{k-1}-\ldots-a_{k}$ is called the companion polynomial of $x$. If we assume that the coefficients $a_{i}$ come from a field $K$ we can write

 $F_{x}=(u-u_{1})^{e_{1}}\cdots(u-u_{t})^{e_{t}}$

where $u_{1},\ldots,u_{t}$ are the distinct roots of $F_{x}$ in some splitting field of $F_{x}$ containing $K$ and $e_{1},\ldots,e_{t}$ are positive integers. A theorem about such recurrence relations is that

 $x_{n}=\sum_{i=1}^{t}g_{i}(n){u_{i}}^{n}$

for some polynomials $g_{i}$ in $K[X]$ where $deg(g_{i}).

Now suppose further that all $K=\mathbb{C}$ and

let $U$ be the largest value of the $|u_{i}|$.

It follows that if $U>1$ then

 $|x_{n}|\leq CU^{n}$

for some constant $C$.

(to be continued)

Title linear recurrence LinearRecurrence 2013-03-22 16:52:29 2013-03-22 16:52:29 Mathprof (13753) Mathprof (13753) 8 Mathprof (13753) Definition msc 11B37