linear recurrence


A sequenceMathworldPlanetmath x0,x1,, is said to satisfy a general linear recurrence if there are constants an,i and fn such that

xn=i=1nan,ixn-i+fn

The sequence {fn} is called the non-homogeneous part of the recurrence.

If fn=0 for all n then the recurrence is said to be homogeneousPlanetmathPlanetmath.

In this case if x and x are two solutions to the recurrence, and A and B are constants, then Ax+Bx are also solutions.

If an,i=ai for all i then the recurrence is called a linear recurrence with constant coefficients. Such a recurrence with an,i=0 for all i>k and ak0 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 sequenceMathworldPlanetmath is a linear recurrence with constant coefficients and order 2.

Now suppose that x={xn} satisfies a homogeneous linear recurrence of finite order k. The polynomialPlanetmathPlanetmath Fx=uk-a1uk-1--ak is called the companion polynomial of x. If we assume that the coefficients ai come from a field K we can write

Fx=(u-u1)e1(u-ut)et

where u1,,ut are the distinct roots of Fx in some splitting fieldMathworldPlanetmath of Fx containing K and e1,,et are positive integers. A theorem about such recurrence relations is that

xn=i=1tgi(n)uin

for some polynomials gi in K[X] where deg(gi)<ei.

Now suppose further that all K= and

let U be the largest value of the |ui|.

It follows that if U>1 then

|xn|CUn

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