# 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=\u2102$ 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 |