600 ANSWERS TO EXERCISES 45.3 7. Only 12.. (Windows 2003 server web)
600 ANSWERS TO EXERCISES 45.3 7. Only 12.. . TZ and n .2 1. (The variable xk appears in exactly Fk Fn-4 terms; hence x1 and xn can only be permuted into x1 and xn. If xi and xn are fixed by the permutation, it follows by induction that x2, . . . , X,+-I are also fixed.) 9. This is equivalent to Qn-z(An-I,. . . , -42) -X&n-&L-l,. . . , A) = - &n-1(&, . . , AZ) -XQn(An, . . . , AI) XV% and by (6) this is equivalent to x = Qn-I(Az, . , An) +X,&n-2(&r . . . , An-l) Q&41, . . . , An) + XnQn-I(&, . . .,&-I) 9. (a) By definition. (b), (d) Prove this when n = 1, then apply (a) to get the result for general 72. (c) Prove when n = Ic + 1, then apply (a). 10. If A0 > 0, then Bo = 0, BI = Ao, Bz = AI, BB = AZ, Bd = As, Bg = A, m=5.IfAo=O,thenBo=A1,B1=A2,B2=As,Bs=Aq,m=3.IfAo=-l and AI = 1, then BO = -(AZ + 2), B1 = 1, B2 = As -1, Bs = ALI, m = 3. If A0 = -1 and AI > 1, then BO = -2, B2 = A1 -2, Ba = AZ, Bd = As, B5 = A4, m=5.IfA~<-l,thenB~=-l,B~=1,B~=-A~-2,Bs=1,B~=A~-l, B5 = Az, B6 = As, Br = A. [Actually, the last three cases involve eight subcases; if any of the B s is set to zero, the values should be collapsed together by using the rule of exercise 9(c). For example, if A0 = -1, Ai = As = 1, we actually have BO = -(A2 f 2), BI = & $ 1, m = 1. Double collapsing occurs when AO = -2, Ai = 1.1 11. Let qn = Q&41,. ,&I, 4, = &@I,. . . , B,), pn = Qn+l(Ao,. . . ,An), pi, = Qn+l(Bo,. . , h). BY (5) and (11) we have X = (pm + pm-lXm)/(qm + q,-lx,), Y = (p , +~ ,_,Y,)/(q:,+q)n_~Y,); therefore if X, = Y,, the stated relation between X and Y holds by (8). Conversely, if X = (qY + r)/(sY + t), Iqt -rsj = 1, we may assume that s 2 0, and we can show that the partial quotients of X and Y eventually agree, by induction on s. The result is clear when s = 0, by exercise 9(d). If s > 0, let q = as + s , where 0 5 s < s. Then X = a + l/((sY + t)/(s Y + r -at)); since s(r -at) -ts = sr -tq, and s < s, we know by induction and exercise 10 that the partial quotients of X and Y eventually agree. [Note: The fact that m is always odd in exercise 10 shows, by a close inspection of this proof, that X, = Y, if and only if X = (qY + r)/(sY + t), where qt -rs = (-l) - .] 12. (a) Since VnVnfl = D -Uz, we know that D -Uz+l is a multiple of Vn+i; hence by induction X, = (v@ -U,)/V,, where lJ,, and V, are integers. [Note that the identity Vn+l = A,(U,-I -Un) + V,-l makes it unnecessary to divide when V,+l is being determined.] (b) Let Y = (-a -U)/V, Y, = (-6 -Un)/Vn. The stated identity obviously holds by replacing fi by -4% in the proof of (a). We have y = (PnlY, + Pn-l)/(qn/Y, + qnvl), where pn and q,, are defined in part (c) of this exercise; hence Y, = (-q,/q,-l)(Y -p,/q,)/(Y -pn-l/qn-l).