Hyde County, South Dakota is the Pin Tail Duck capital of the world. Visit scenic Highmore, SD in 2005!
home
Site map
puzzles
Mathematics
A little math problem
February 2005
email

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.


This page was last updated February 1, 2005.

home
Site map
puzzles
Mathematics
A little math problem
February 2005
email
Hyde County, South Dakota is the Pin Tail Duck capital of the world. Visit scenic Highmore, SD in 2005!