Date: Thu, 7 Mar 1996 02:59:19 -0500 (EST)
From: [Permission pending]
To: Dave Rusin <rusin@math.niu.edu>
Subject: Re: Q: "Skipping" continued fraction convergents?

On Wed, 6 Mar 1996, Dave Rusin wrote:

> Of course for certain continued fractions there is a pattern to
> the convergents  (p_n/q_n); for example in 1/1+1/1+1/1+ ..., the convergents
> are of the form  p_n= a r^n + b/r^n  for some easy constants  a  and  b,
> where  r  is the golden ratio; in particular,  p_n  is the nearest integer
> to  [a r^n ].
> 
> dave
> 
> (If you do hear of something speedier I'd like to hear about it.)
> 

The reason I was curious is that I just found out that you can
calculate the nth Chebyshev polynomial w/o going through all of th
preceding ones (should have saved the message...something like
T(m+n)(x) = T(m)(x) T(n)(x) - T(|m-n|)(x), but don't quote me), and
since they satisfy 2-term recurrence relations the same as continued
fractions do, perhaps the technique carries over.

Thanks for the input.
[Permission pending]

==============================================================================
(The TChebyschev polynomials satisfy  T_(n+1)(x) = 2x T_n(x) - T_(n-1)(x),
which is to say they satisfy a linear recurrence relation whose coefficients
are _constants_, that is, _independent of  n_. In this way they are more 
similar to the Fibonnacci numbers, and yes indeed they can be easily calculated
for large  n. Note we need only apply high powers of the matrix
	[ 2x  -1 ]
	[ 1    0 ]
to the column matrix  [T_1, T_0]. High powers of a matrix can be computed
in  logarithmic time by repeated squarings.) -- djr
==============================================================================