linear recurrence

A sequence $x_0,x_1,\mathrm{\dots },$ 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+B{x}^{\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\ne 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}-\mathrm{\dots }-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}\mathrm{\cdots }{(u-u_t)}^{e_t}$$

where $u_1,\mathrm{\dots },u_t$ are the distinct roots of $F_x$ in some splitting field of $F_x$ containing $K$ and $e_1,\mathrm{\dots },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 .

Now suppose further that all $K=ℂ$ and

let $U$ be the largest value of the $|u_i|$.

It follows that if $U>1$ then

$$|x_n|\le C{U}^n$$

for some constant $C$.

(to be continued)

Title	linear recurrence
Canonical name	LinearRecurrence
Date of creation	2013-03-22 16:52:29
Last modified on	2013-03-22 16:52:29
Owner	Mathprof (13753)
Last modified by	Mathprof (13753)
Numerical id	8
Author	Mathprof (13753)
Entry type	Definition
Classification	msc 11B37