602 ANSWERS TO EXERCISES 45.3 on output: X3 (How to cite a web site)
602 ANSWERS TO EXERCISES 45.3 on output: X3 -1 5 1 1 1 2 1 2 Co xk 39 97 -58 -193 -2 -25 -62 37 123 2 16 53 3 5 17 22 7 1 2 3 5 1 3 1 4 5 14 1 2 1 3 7 1 2 7 9 25 12 1 0 1 2 2 1 co 0 M. Mend&s France has shown that the number of quotients output per quotient input is asymptotically bounded between l/r and r, where r = 2]K( lad -bc])/2] + 1 and K is the function defined in exercise 38; this bound is best possible. [Topics in Number Theory, ed. by P. Turan, Colloquia Math. Sot. Jrinos Bolyai 13 (1976), 183-194.1 Gosper has also shown that the above algorithm can be generalized to compute the continued fraction for (azy + bx + cy + d)/(Axy + Bx + Cy + D) from those of x and y (in particular, to compute sums and products). [MIT AI Laboratory Memo 239 (Feb. 29, 1972) Hack 101.1 16. It is not difficult to prove by induction that fn(z) = 2/(2n + 1) + O(z3) is an odd function with a convergent power series in a neighborhood of the origin, and that it satisfies the given differential equation. Hence jr(z) = /z-l + fl(Z)/ = = /z-l, 32-l,. . . ) (2n + l)z- + fn+l(z)/. It remains to prove that lim,,, /z-l, 32-l , . , (2n + l)z- / = fo(z). [Actually Euler, age 24, obtained continued fraction expansions for the considerably more general differential equation f;(z) = uzm + bf,(z)z - + cf,(z) ; but he did not bother to prove convergence, since formal manipulation and intuition were good enough in the eighteenth century.] There are several ways to prove the desired limiting equation. First, letting f&) = c, %kZk, we can argue from the equation (2n + 1)&l + (2n + 3)a,3z2 + (2n + 5)a,sz4 + . . . = 1 - (U,lZ + u,sz3 + a,5z5 + ) that (-l)ka,(zk+l) is a sum of terms of the form ck/(2n+l)k+ (2n+bk,). . . (2n+bkk), where the ck and bkm are positive integers independent of 72. For example, we have –an7 = 4/(2n + 1)4(2n + 3)(2n + 5)(2n + 7) + 1/(2n + 1)4(2n + 3)2(2n + 7). Thus ]a(,+i)k] 5 l&k], and ]fn(z)] 5 tan]z] for ]z] < r/2. This uniform bound on fn(z) makes the convergence proof very simple. Careful study of this argument reveals that the power series for fn(z) actually converges for ]z] < adm/2; this is interesting, since it shows that the singularities of fn(z) get farther and farther away from the