A076839

[Roland Bacher]

> Hello, concerning Mr Propp's comment in
> 
> %C A076839 Any sequence a(1),a(2),a(3),... defined by the recurrence a(n) = (a(n-1)+1)/a(n-2) (for n>2) has period 5. The theory of cluster algebras currently being developed by Fomin and Zelevinsky gives a context for these facts, but it doesn't really explain them in an elementary way. - James Propp, Nov 20, 2002
> %H A076839 Sergey Fomin and Andrei Zelevinsky, <a href="http://arXiv.org/abs/math.RA/0208229">Cluster algebras II: Finite type classification</a>
> 
> This would be too long for the entry (for simplicity with indices 0-5):
> 
> $$a_2=\frac{a_1+1}{a_0} \qquad 
> a_3=\frac{\frac{a_1+1}{a_0}+1}{a_1}=\frac{a_1+a_0+1}{a_0a_1}$$
> $$a_4=\frac{\frac{a_1+a_0+1}{a_0a_1}+1}{\frac{a_1+1}{a_0}}=
> \frac{a_1a_0+a_1+a_0+1}{(a_1+1)a_1}=\frac{a_0+1}{a_1}$$
> $$a_5=\frac{\frac{a_0+1}{a_1}+1}{\frac{a_1+a_0+1}{a_0a_1}}=
> \frac{\frac{a_1+a_0+1}{a_1}}{\frac{a_1+a_0+1}{a_0a_1}} = a_0\qed$$
> 
> thus a(n+5)=a(n) (1,1,2,3,2).
> G.f. (1+x+2x^2+3x^3+2x^4)/(1-x^5).
> Closed form is a mess with 1.8 + 5th roots...
> Any periodic sequence has such a GF.
> 
> Now, more interestingly, how do you get from any such GF to rational
> (or is it quadratic?) recursions like the above, e.g. A(x)=.../(1-x^7)? 
> Hypergeometry?
> 
> 
> ralf


The above recursion yields a polynomial application of finite order (five)
of the projective plane:

(x,y,z)   |---->   ( (x+z)z, xy , xz )

after homogeneisation.

Any polynomial application of the projective 
k-space having finite order and the form

(x1,x2,x3,.. ,xk,t)  |---> (f(x1,.. ,xk,t),x1,x2,...,x(k-1),t)

(where f is a homogeneous rational fraction of degree 1)

can be turned into a recursive formula yielding periodic sequences.

Roland Bacher