Linear Fractional Recurrences: Periodicities and Integrability

Eric Bedford, Kyounghee Kim

We consider k-step recurrences of the form z_{n+k} = A(z)/B(z), where A and B are linear functions of z_n, z_{n+1}, \dots, z_{n+k-1}, which we call k-step linear fractional recurrences. The first Theorem in this paper shows that for each k there are k-step linear fractional recurrences which are periodic of period 4k. Among this class of recurrences, there is also the so-called Lyness process, which has the form $A(z)/B(z) = (a z_n + z_{n+2} + ... + z_{n+k-1})/z_{n+1}. The second Theorem shows that the Lyness process has quadratic degree growth. The Lyness process is integrable, and we discuss its known integrals.