A076839

[Ralf Stephan]

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