A little math problem – answer
Let T(k) be the transformation
x -> k/(1-x).
SolutionLet 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**nwhere x1 and x2 are the roots of the quadratic equation
x**2 - x + k = 0and 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.
This page was last updated February 1, 2005.