Affordable web hosting - 45.3 ANALYSIS OF EUCLID S ALGORITHM 349 Thus everything
45.3 ANALYSIS OF EUCLID S ALGORITHM 349 Thus everything hinges on our being able to prove that Un produces small function values, where U is the linear operator defined in (29). Note that U is a positive operator, in the sense that Ucp(x) 2 0 for all x if (o(x) 2 0 for all x. It follows that U is order-preserving: If (01(x) 5 ps(x) for all x then we have V(oi(x) 5 Upz(x) for all x. One way to exploit this property is to find a function yo for which we can calculate Up exactly and to use constant multiples of this function to bound the ones that we are really interested in. First let us look for a function g such that Tg is easy to compute. If we consider functions defined for all x > 0, instead of only on [0, 11, it is easy to remove the summation from (25) by observing that SG(x+l)-SG(x) = G(&)-;A&&) =$$+W (35) when G is continuous. Since T((l + x)G ) = (1 + x)(SG) , it follows (see exercise 20) that –Tdx) Tdx+ 1) = -&)g(&>* (36) x+1 (& x+2 If we set Tg(x) = l/(x + l), we find that the corresponding value of g(x) is 1 -j-x -l/(1 + x). Let p(x) = g (x) = 1 + l/(1 + x)~, so that Up(x) = -(Tg) (x) = l/(1 + x)~; th is is the function (o we have been looking for. For this choice of cp we have 2 2 p(x)/Up(x) = (1 + x)~ + 1 5 5 for 0 5 x 5 1, hence i(P I UP I 3P. By the positivity of U and p we can apply U to this inequality again, obtaining &p < 4Up 2 U2p < 3Up 5 $(p; and after n - 1 applications we have 5- (0 5 unp 2 2-Q (37) for this particular (o. Let x(x) = &(x) = 1 be the constant function; then for 0 5 x 2 1 we have ix < (o 5 2x, hence It follows by (33) that s #(ln2)25-n 5 (-l)nRK(x) 2 +j(ln2)22-n, for 0 < 2 5 1; hence by (30) and (34) we have proved the following result: Theorem W. The distribution F,(x) equals lg(1 + x) + 0(2- ) as n –+ 00. In fact, F,(x)-lg(1 -j-x) lies between &(-l)nf15-n(ln(l+x))(ln2/(1+x)) and ~(-l)n+12-n(ln(l + x))(ln2/(1+ x)),, for 0 2 x 5 1. 1