**
**# A little math problem – answer

__Problem Statement__

Let T(k) be the transformation
x -> k/(1-x).

For certain values of k T(k) defines a cyclic group. For example,

for k = 1 we have the sequence
{x, 1/(1-x), x-1/x}.

Oddly enough the only rational values of k
for which T(k)

defines a cyclic group are 1, 1/2, and 1/3. Please explain why.

__Solution__

Let Q(n,x,k) be the sequence generated by T(k) where
Q(1,x,k)=x,
Q(2,x,k)=k/(1-x),
...
Q(n+1,x,k)=k/(1-Q(n,x,k)).

It is readily seen that we have
(1) Q(n,x,k) = k*P(n-1,x,k)/P(n,x,k)

where P is the recurrence relationship defined by
(2) P(0,x,k) = x/k
P(1,x,k) = 1
P(n,x,k) = P(n-1,x,k) - k*P(n-2,x,k)

Equation (2) holds for all x. In particular it holds for x=0;
it suffices therefore to consider the recurrence
p(0,k) = 0
p(1,k) = 1
p(n,k) = p(n-1,k)-k*p(n-2,k)

The recurrence p can be expressed directly as
(3) p(n,k) = a1*x1**n + a2*x2**n

where x1 and x2 are the roots of the quadratic equation
x**2 - x + k = 0

and a1 and a2 are chosen so as to satisfy the initialization
conditions. We observe that if the roots of (4) are real then
there cannot be an infinite number of zeroes in the sequence
p(n,k); ergo it is necessary that the roots be complex, which
in turn implies that k>1/4.
Now consider the sequence of polynomials, p(n,k). The first few are

p(0,k) = 0
p(1,k) = 1
p(2,k) = 1
p(3,k) = 1-k
p(4,k) = 1-2k
p(5,k) = 1-3k+k**2
...

It is readily seen that they all have integer coefficients and that in
each the leading term is 1. It follows that for k to be a rational root of p(n,k)=0
we must have k=1/m for some integer m. Since we have already shown
that must be greater than 1/4 it follows that m must either be 1, 2, or 3.
It is readily verified that each value of m defines a cyclic group.