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 partof 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 calleda linear recurrence with constant coefficients. Such a recurrencewith $a_{n,i}=0$ for all $i>k$ and $a_k\ne 0$ is said to be offinite order and the smallest such integer $k$ is called theorder of the recurrence. If no such $k$ exists, the recurrence issaid 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 offinite order $k$. The polynomial$F_x=u^k-a_1{u}^{k-1}-\mathrm{\dots }-a_k$ is called the companion polynomialof $x$.If we assume that the coefficients $a_i$ come from a field $K$ we canwrite

$$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 somesplitting field of $F_x$ containing $K$ and $e_1,\mathrm{\dots },e_t$ arepositive 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)