A little math problem – answer
Problem Statement
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 = 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. |