recurrence relation - period?

lajanugen · Poincare Conjecture Offline Joined: 31 Aug 2008 Posts: 115

Hello. Given a recurrence relation, is it possible to determine whether the sequence perodically recurs? If so , then is there a way to determine its period?
I'm novice to the theory of recurrence relations, so please anyone kindly recommend some articles or texts i should work on to develop my skills on the subject
Thankyou

**Posted:** Wed Mar 04, 2009 4:38 am

t0rajir0u

There are some easy special cases. If the recurrence is linear, this is possible if and only if the roots of the characteristic polynomial of the recurrence are roots of unity (edit: and either the roots are of multiplicity $1$ or the initial conditions are chosen appropriately). For example, $a_{n + 2} = a_{n + 1} - a_n$ has characteristic polynomial $x^2 - x + 1$ , whose roots are the primitive sixth roots of unity, so this recurrence has period $6$ . See the discussion here (especially Altheman's link at the bottom for a more systematic approach).

If the recurrence is of the form $x \mapsto \frac {ax + b}{cx + d}$ , this is possible if and only if some power of the matrix $\left[ \begin{array}{cc} a & b \\ c & d \end{array} \right]$ is a multiple of the identity (i.e. has finite order in $PSL_2(\mathbb{C})$ ). This can also be determined by computing the characteristic polynomial. See the discussion here, which applies these ideas to a different question.

Finally, there are some very specific tricks involving trigonometric identities. Every periodic recurrence I have seen on a contest has been of one of these forms.

_________________
Annoying Precision (http://qchu.wordpress.com/)

lajanugen · Poincare Conjecture Offline Joined: 31 Aug 2008 Posts: 115

Thankyou very much t0rajir0u

**Posted:** Wed Mar 04, 2009 10:51 am