The Chebyshev polynomials T_n are defined for integer n\ge0 by
T_n(x)=\cos(n\cos^{-1}x), \qquad |x|\le1.
We have T_0(x)=1, T_1(x)=x and, for n\ge2,
T_n(x)=2xT_{n-1}(x)-T_{n-2}(x).
See Rivlin [4], for example, for a description of these and their
properties.
In this note we shall largely be concerned with the polynomials X_{p,n}
defined for integers p\ge2 and n\ge0 by
X_{p,n}(x)=2\cos\(p^n\cos^{-1}\frac x2\), \qquad |x|\le2. \tag1.1
Apart from some scaling, these are the Chebyshev polynomials T_{p^n}.
Notice that X_{p,0}(x)=x for all p. When no confusion is likely, we
shall write X_{p,n} to stand for X_{p,n}(x).
We shall concentrate for the moment on the case p=2, writing X_n in
place of X_{2,n}. Thus,
X_n=2\cos\(2^n\cos^{-1}\frac x2\), \qquad |x|\le2. \tag1.2
From (1.2),
2^{n+1}\cos^{-1}\frac x2=2\cos^{-1}\frac{X_n}2,
so that, using (1.2) again,
X_{n+1}=2\cos\(2\cos^{-1}\frac{X_n}2\).
From the trigonometric identity \cos2\theta=2\cos^2\theta-1, we thus have
X_{n+1}=X_n^2-2, \qquad X_0=x. \tag1.3
Conversely, the sequence of polynomials defined by (1.2) can be thought of as
the closed-form solution of the first-order recurrence relation (1.3), when
|x|\le2.
It can be verified that the closed-form solution of (1.3) when |x|>2
is
X_n=2\cosh\(2^n\cosh^{-1}\frac x2\). \tag1.4
Proceeding in the same manner in the general case, we may view (1.1) as the
closed-form solution of the first-order recurrence relation
X_{p,n+1}=2\cos\(p\cos^{-1}\frac{X_{p,n}}2\),
\quad X_{p,0}=x, \quad |x|\le2, \tag1.5
with a solution corresponding to (1.4) when |x|>2. The familiar identity
expressing \cos p\theta as a polynomial in \cos\theta gives an
alternative form involving an explicit polynomial of degree p in
X_{p,n}. As a further example, take p=3 and write X_n for X_{3,n}:
the closed-form solution of
X_{n+1}=X_n^3-3X_n, \qquad X_0=x, \tag1.6
is
X_n=\cases 2\cos\(3^n\cos^{-1}\dfrac x2\), & |x|\le2, \\
2\cosh\(3^n\cosh^{-1}\dfrac x2\), & |x|>2. \endcases
We shall write f_p to denote the polynomial on the right of (1.5), so that
f_p(\xi)=2\cos\(p\cos^{-1}\frac\xi2\), \qquad |\xi|\le2. \tag1.7
In fact, f_p(\xi)=2T_p(\xi/2) and, in particular, as we have seen,
f_2(\xi)=\xi^2-2 and f_3(\xi)=\xi^3-3\xi.
The aim of this paper is to investigate these recurrence relations and their closed-form solutions further, and to consider the various inverse recurrence relations, to be defined in terms of inverses of f_p when f_p has a suitably restricted domain. \bigpagebreak \bf
\rm
Let a_1, ..., a_{p-1} denote the zeros of f'_p(\xi), so, in fact,
a_m=2\cos\frac{m\pi}p, \qquad m=1,2,...,p-1.
In each interval [-2,a_{p-1}], [a_{p-1},a_{p-2}], ..., [a_1,2], the
polynomial f_p is monotone, so there are p naturally associated inverse
functions. Let f_p^{-1} denote any one of these inverses. Comparing (1.1)
and (1.7), we observe that f_p=X_{p,1} and that in precisely the same way
there are p^n natural inverse functions that may be associated with the
polynomial X_{p,n}. Let X_{p,n}^{-1} denote any one of these.
In any such situation, we have the following result. We have dispensed here with the subscript~p, and we have written g for f_p, so that the result can be given in some generality.
\proclaim{Theorem}
{Let X_{n+1}(x)=g(X_n(x)) be a given recurrence relation,
with X_0(x)=x. Consider the recurrence relation
Y_{n+1}(y)=g_{n+1}^{-1}(Y_n(y)), \quad Y_0(y)=y, \tag2.1
where g_n^{-1} denotes an inverse function g^{-1} chosen
separately for each n. For each n\ge1, there exists a unique choice
of X_n^{-1} so that Y_n(y)=X_n^{-1}(y).}
{\sc Proof:} Take any positive integer n. We set
x=g_n^{-1}(g_{n-1}^{-1}(\cdots(g_1^{-1}(y))\cdots)).
Then y=g(g(\cdots(g(x))\cdots)), with n applications of g; but this
is X_n(x). Since x is fixed by y, this determines a unique X_n^{-1}
such that x=X_n^{-1}(y), and then, from (2.1),
Y_n(y)=g_n^{-1}(Y_{n-1}(y))=...
=g_n^{-1}(g_{n-1}^{-1}(\cdots(g_1^{-1}(y))\cdots))
=x=X_n^{-1}(y),
as required.
We call the recurrence relation (2.1) an inverse of the recurrence relation X_{n+1}(x)=g(X_n(x)), X_0(x)=x.
As an example, consider again the recurrence relation (1.3), namely
X_{n+1}=X_n^2-2, \quad X_0=x,
for |x|\le2. Here g(\xi)=\xi^2-2. We shall first choose
g^{-1}(\xi)=\sqrt{\xi+2} (rather than the negative root, for all n), so
that our inverse recurrence relation is
Y_{n+1}=\sqrt{Y_n+2}, \quad Y_0=y, \quad |y|\le2. \tag2.2
As we know,
X_n(x)=2\cos\(2^n\cos^{-1}\frac x2\), \qquad |x|\le2.
We must determine X_n^{-1} from the functions
2\cos\frac{\cos^{-1}(\xi/2)+2k\pi}{2^n},
\quad |\xi|\le2, \quad k=0,1,...,2^n-1. \tag2.3
It can be verified by substitution that, for each n, taking k=0 works
for us. Since, by the Theorem, there is only one correct choice, we may
assert that the closed-form solution of this inverse recurrence relation is
Y_n=2\cos\frac{\cos^{-1}(y/2)}{2^n}.
The recurrence relation (2.2) has been previously investigated by, for
example, Paris [3] and Chorlton [1], but the closed-form solution given
here has not been used. In particular, Chorlton takes y=2^{1/2} and
writes
Y_n=(2+(2+(2+\cdots(2)^{1/2})^{1/2})^{1/2})^{1/2},
where there are n square roots, and states that the general form for
Y_n ``cannot be expressed more compactly''. However, Spiegel [5] gives
this as Exercise 5.142, with y=0 which is equivalent, and gives the
answer Y_n=2\cos(\pi/2^{n+1}). This of course agrees with our closed-form
solution, and in this special case may be obtained by more direct means.
Among other recurrence relations which are inverses of (1.3), we may consider
Y_{n+1}=-\sqrt{Y_n+2}, \quad Y_0=y, \quad |y|\le2, \tag2.4
and
Y_{n+1}=(-1)^n\sqrt{Y_n+2}, \quad Y_0=y, \quad |y|\le2. \tag2.5
As may be verified by substitution, but not very easily, the closed-form
solution of (2.4) is
Y_n=-2\cos\(\frac\pi3\(1-\frac1{(-2)^{n-1}}\)
-\frac{\cos^{-1}(y/2)}{(-2)^n}\).
This solution was in fact obtained by considering first the recurrence
relation
Z_{n+1}=\sqrt{2-Z_n}, \quad Z_0=z, \quad |z|\le2,
which has the alternative formulation
Z_{n+1}=2\sin\frac{\cos^{-1}(Z_n/2)}2, \quad Z_0=z, \quad |z|\le2.
An inductive investigation produced the closed-form solution
Z_n=2\cos\(\frac\pi3\(1-\frac1{(-2)^n}\)
+\frac{\cos^{-1}(z/2)}{(-2)^n}\).
Taking Y_n=-Z_n and y=-z, and since
\cos^{-1}(-\theta)=\pi-\cos^{-1}\theta, we obtain (2.4) and the solution
given above.
A similar approach was used on (2.5), producing the following as its
closed-form solution:
Y_n=\cases
\dsize\phantom-2\cos\(\frac{2\pi}5\(1-\frac1{2^n}\)+\frac{\cos^{-1}(y/2)}{2^n}\),
& \text{if }n\equiv0 \text{ (mod 4)}, \\
\dsize-2\cos\(\frac\pi5\(1-\frac1{2^{n-1}}\)+\frac{\cos^{-1}(y/2)}{2^n}\),
& \text{if }n\equiv1 \text{ (mod 4)}, \\
\dsize\phantom-2\cos\(\frac{2\pi}5\(1+\frac1{2^n}\)-\frac{\cos^{-1}(y/2)}{2^n}\),
& \text{if }n\equiv2 \text{ (mod 4)}, \\
\dsize-2\cos\(\frac\pi5\(1+\frac1{2^{n-1}}\)-\frac{\cos^{-1}(y/2)}{2^n}\),
& \text{if }n\equiv3 \text{ (mod 4)}. \endcases
The general recurrence relation inverse to (1.3) can be given as
Y_{n+1}=m(n)\sqrt{Y_n+2}, \quad Y_0=y, \quad |y|\le2, \tag2.6
where the function m has codomain \{-1,1\}. The required value of k
in (2.3) for each~n is difficult to establish functionally, as the
preceding two examples would testify, but for small values of n is easy
to find computationally. For nine choices of m(n), the table below
gives the required values of k for 1\le n\le 15. The first two choices
are m_1(n)=-1 and m_2(n)=(-1)^n, which correspond to the recurrence
relations (2.4) and (2.5), above. The remaining choices are most simply
described as choices of signs, in order for n\ge0: m_3(n) is the
sequence +, -, +, repeated; m_4(n) is the sequence -, +, -,
repeated; m_5(n) is the sequence +, +, -, repeated; m_6(n) is
the sequence +, -, -, -, repeated; m_7(n) is the sequence +,
+, -, -, repeated; m_8(n) is the sequence +, +, +, -,
repeated; finally, and most ``randomly'' of these, m_9(n) is the sequence
+, +, -, +, -, -, +, repeated.
Notice that the general inverse recurrence relation (2.6) can be given in
the deceptively easy form
Y_n=Y_{n+1}^2-2, \quad Y_0=y, \quad |y|\le2,
and that this can be written down immediately from (1.3).
\topinsert
\def\h{\hfil} \def\mtrule{\multispan{22}\hrulefill\cr}
\newdimen\digitwidth \setbox0=\hbox{\rm0}
\digitwidth=\wd0 \catcode`"=\active \def"{\kern\digitwidth}
\bf
\rm
Much of the impetus for this work was a reconsideration of the paper of Cohen and Shannon [2], which described the geometrical approach in 1707 of John Ward [6] to the calculation of \pi.
Based on successive trisections of the arc of a circle, Ward deduced a
family of polynomial equations derived from the recurrence relation
Y_n=3Y_{n+1}-Y_{n+1}^3, \quad Y_0=1. \tag3.1
In the present treatment, we consider this to be an inverse of the relation
X_{n+1}=3X_n-X_n^3, \quad X_0=x. \tag3.2
The specific inverse required by Ward is that which gives the smallest
positive value for Y_n, for each n. In that case, the geometry of
Ward's argument implied that 3^{n+1}Y_n\to\pi as n\to\infty.
The recurrence relation (3.2) is similar to (1.6). For (3.2), the closed-form
solution is
X_n=2\sin\(3^n\sin^{-1}\frac x2\).
Therefore, for (3.1) our theorem gives
Y_n=2\sin\frac{(\pi/6)+2k\pi}{3^n},
with k chosen from \{0,1,...,3^n-1\} to have Y_n as described
above. It is easy to show that in fact we require k=0 for all n and then
it is easy to confirm that 3^{n+1}Y_n\to\pi.
This explicit reasoning was not available to Ward (or to the authors of
[2]), and indeed it does not further the problem of estimating \pi.
Instead, Ward used his polynomial equations, as follows. From (3.1), we have
Y_1^3-3Y_1-1=0; in this, put Y_1=3Y_2-Y_2^3 to give
Y_2^9-9Y_2^7+27Y_2^5-30Y_2^3+9Y_2-1=0. \tag3.3
Ward in fact iterated this process sixteen times to end with a polynomial
equation of degree~15 in~Y_{16}. This was the corresponding equation of
degree 3^{16}, but truncated and with coefficients given to around 16
significant figures. The ingenious, if not fully justified, reasons for
doing this, and the method by which Ward then approximated the smallest
positive root and found \pi to~15 decimal places, are described in~[2].
The equation (3.3) was given in [2], but was not realised then to be T_9(Y_2)=1. The other equations arising from iteration of (3.1) are of the form T_{3^n}(Y_n)=1. This use of Chebyshev polynomials is presumably an original discovery of Ward's, but the appearance of these polynomials can be traced back more than one hundred years earlier. We are indebted to Mr Garry Tee of the University of Auckland for the information that in about 1592 Adrian van Roomen published a challenge, solved by Franciscus Vieta, to solve a certain polynomial equation of degree 45. Vieta apparently recognised it as having the form T_{45}(x)=c, for some constant c.
\item {1.} {F. Chorlton, `Sequences satisfying the form u_n=f(u_{n-1})', Int. J. Math. Ed. Sci. Technol., \bf 24 (1993), 144-146.}
\item{2.} {G. L. Cohen and A. G. Shannon, `John Ward's method for the calculation of pi', Hist. Math., \bf 8 (1981), 133-144.}
\item{3.} {R. B. Paris, `An asymptotic approximation connected with the golden number', Amer. Math. Monthly, \bf 94 (1987), 272-278.}
\item{4.} {T. J. Rivlin, Chebyshev Polynomials, from Approximation Theory to Algebra and Number Theory , Second Edition, New York, Wiley (1990).}
\item{5.} {M. R. Spiegel, Finite Differences and Difference Equations , New York, Schaum's Outline Series, McGraw-Hill (1971).}
\item{6.} {J. Ward, The Young Mathematician's Guide , Third Edition, London, Horne, Bettesworth \& Fayram (1719). [The first edition was published in 1707.]} \ending {University of Technology, Sydney}{} {NSW Bureau of Meteorology, Sydney}