## You are here

Homelinear recurrence

## Primary tabs

# 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})<e_{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)

## Mathematics Subject Classification

11B37*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections