18.100B Analysis I, Solutions to Problem Set 5

18.100B Problem Set 5 Solutions 1) We have X ⊆ M, with M complete. X is complete if and only if every Cauchy sequence of X converges to some x ∈ X. Let (xi ) be Cauchy, with xi ∈ X. M being complete implies that xi → y ∈ M. Therefore y is a limit point of X. So if X is closed, y ∈ X, so every Cauchy sequence converges in X, so X is complete. Conversely, suppose X is complete. Therefore every Cauchy sequence of X converges to a 1 point in X. If y ∈ X � , then we can choose a sequence (xi ) ⊆ X with d(xi , y) < , and since this i converges to y in M, it is Cauchy in X. Thus by completeness it converges in X, and by the uniqueness of limits, y ∈ X. Therefore X � ⊆ X, so X is closed. 2) First, we know that if a sequence converges to some limit L, every subsequence of that sequence converges to L. This implies the ”only if” (⇒) of both (a) and (b). a) To prove the ”if” (⇐) of a), assume the sequences (x2n ) and (x2n−1 ) both converge to the limit L. Then given ε > 0 we can find natural numbers N and N � such that for n > N, n� > N � =⇒ |x2n − L| < ε and |x2n� −1 − L| < ε. Let M = max{2N, 2N � } and notice that if m > M , then |xm − L| < ε regardless of whether m is even or odd. Therefore (xm ) converges to L. b) Here, we reduce to the case of (a). Suppose x2n → A, x2n−1 → B, and x5n → C. Consider the sequence (x10n ). This is a subsequence of (x2n ), so it must converge to A. But is also a subsequence of (x5n ), so it must converge to C. By the uniqueness of limits, we have A = C. Similarly (x10n−5 ) is a subsequence of both (x2n−1 ) and (x5n ), so it must converge to both B and C, so B = C. Thus A = B = C, in particular A = B, so now we can apply (a). 3) For any N ∈ N, {xn + yn |n > N } ⊆ {xm + yn |m, n > N }. Therefore sup (xn + yn ) ≤ sup (xm + yn ) = sup (xm ) + sup (yn ). n>N m,n>N m>N n>N Since this is true for all N ∈ N, it is true in the limit. So lim sup(xn +yn ) ≤ lim sup xn +lim sup yn . By the above, and since lim inf(zn ) = − lim sup(−zn ) for any bounded sequence zn , lim inf(xn + yn ) = − lim sup(−xn − yn ) ≥ − lim sup(−xn ) − lim sup(−yn ) = lim inf(xn ) + lim inf(yn ). Now we assume (xn ) converges to some L. If lim sup yn = α, then some subsequence ynk → α. Since xn → L, any subsequence converges to this limit, so in particular xnk → L. Therefore the sequence (xn + yn ) has a subsequence (xnk + ynk ) that converges to L + α. Therefore lim sup(xn + yn ) ≥ L + α = lim sup xn + lim sup yn ≥ lim sup(xn + yn ), so we have equality. Once again the relation between limsup and liminf exploited above shows that equality also occurs for liminf, when (xn ) converges. 4) We have (xn ) a bounded sequence and (an ) the sequence defined as x1 + x2 + . . . + xn an = . n 1 ε Let α = lim sup xn , and fix 1 > ε > 0. Then ∃N ∈ N such that ∀n > N , xn < α + , by the 2 2BN definition of lim sup xn . Let B be an upper bound for xn . Then if n > , ε an = N n N n � � � α+ xj x1 + x2 + . . . + xn � xi B = + ≤ + 2BN n n n n ε i=1 j=N +1 i=1 ε 2 j=N +1 ≤ ε ε + α + = α + ε. 2 2 So for n large enough, an ≤ α + ε. Therefore lim sup an ≤ α + ε. But ε can be chosen arbitrarily small, so lim sup an ≤ α. This also shows that − lim sup −xn ≤ − lim sup −an , or lim inf xn ≤ lim inf an . So we have lim inf xn ≤ lim inf an ≤ lim sup an ≤ lim sup xn . If xn → x, then lim inf xn = lim sup xn = x, so by the inequality lim inf an = lim sup an = x, so an → x. However, (an ) can converge without (xn ) converging. For example, let xn = (−1)n . Then ⎧ ⎨ 1 − n odd, an = n ⎩0 n even. Since both even and odd subsequences converge to 0, an → 0. (xn ), on the other hand, has its odd subsequence converging to -1 and its even subsequence converging to 1 (they are both constant subsequences). So (xn ) does not converge. √ √ 5) We have that 0 < x < 1 and xn = 1 − 1 − xn−1 . Since the functions 1 − x and x both take the open interval (0, 1) to itself, by induction 0 < xn < 1 ∀n ∈ N. For any n ∈ N, we have � � 1 − 1 − xn−1 = xn =⇒ 1 − xn−1 = 1 − xn =⇒ 1 − xn−1 = (1 − xn )2 < 1 − xn since 0 < (1 − xn ) < 1. This shows that xn−1 > xn , so the sequence is decreasing. Therefore the sequence is decreasing and bounded below by 0, so it must have a limit L ≥ 0. Suppose L > 0. Then (1 − L)2 < 1 − L < 1, since it is clear by L < x1 < 1 that L < 1 ((xn ) is strictly decreasing, so L < xn ∀n ∈ N). Therefore 1 − (1 − L)2 > L, so ∃n ∈ N such that √ √ 1 − (1 − L)2 > xn =⇒ (1 − L)2 < 1 − xn =⇒ 1 − L < 1 − xn =⇒ L > 1 − 1 − xn = xn+1 > L. This gives L > L, a contradiction. Therefore L = 0. xn+1 Now to calculate the limit of . We have xn √ √ √ xn+1 1 − 1 − xn (1 − 1 − xn ) · (1 + 1 − xn ) 1 − (1 − xn ) √ √ lim = lim = lim = lim n→∞ xn n→∞ n→∞ n→∞ xn (1 + 1 − xn ) xn xn (1 + 1 − xn ) xn 1 1 1 √ √ √ = lim = lim = = . n→∞ xn (1 + 1 − xn ) n→∞ 1 + 1 − xn 2 1+ 1−0 We can substitute the limit of xn into the limit because the function at 0, the limit of (xn ). 1 √ is continuous 1+ 1−x 6) a) So the defining equation for Φ is a b = b c where a = b + c. So c · (b + c) = b · b which gives � b �2 � b � = + 1 =⇒ Φ2 = Φ + 1 c c Φ= Using the quadratic formula with x2 − x − 1 = 0, which Φ satisfies, we get √ 1± 5 Φ= 2 and since Φ was defined to be greater than 1, the ± sign must be a + sign. b) We want to show that 1 Φ=1+ , 1 + 1+ 1 1 1 1+ 1+··· 1 . xn−1 First we must show that (xn ) converges. It is clear that xn > 0, ∀n ∈ N. Now this gives 1 1 that, since xn = 1 + , xn ≥ 1, ∀n ∈ N. And this implies ≤ 1, which gives that xn−1 xn 1 xn+1 = 1 + ≤ 2. So 1 ≤ xn ≤ 2. Now consider x2n−1 , the odd terms of the sequence. The xn first few are: 1 1 x1 = 1 x3 = 1 + x5 = 1 + 1 1+ 1 1 + 1+ 1 1 where the right hand side is the limit of the sequence xn where x1 = 1 and xn = 1 + 1+ 1 1 Analyzing these, we see that x1 < x3 < x5 < . . .. This is because to get from x2n−1 to x2n+1 , you add a positive number to an even-numbered denominator of the continued fraction, which 1 makes it greater. Since x2n = 1 + , the even subsequence is 1 more than the inverses x2n−1 of the odd sequence, which is increasing, so the even subsequence is decreasing. Since these subsequences are both bounded between 1 and 2 and are monotonic, they must have limits, say x2n−1 → a and x2n → b. We have a = lim x2n+1 = lim 1 + n→∞ n→∞ 1 1+ 1 x2n−1 =1+ 1 1+ 1 lim x2n−1 =1+ 1 . 1 + a1 1 1 1 a(1 + ) = (1 + ) + 1 =⇒ a + 1 = 2 + =⇒ a2 = a + 1. a a a But this is exactly the quadratic equation that Φ satisfies. Since a ≥ 1, a = Φ. Exactly the same argument works for b, since the relation between x2n+2 and x2n is identical. Therefore b = Φ, which implies (by problem 2) that xn → Φ. c) Now we want to show that yn → Φ for the sequence (yn ) defined by � y1 = 1, and yn = 1 + yn−1 . It is clear that yn ≥ 1, since by induction yn2 = 1 + yn−1 ≥ 2. Also, y1 < Φ and � √ yn−1 < Φ =⇒ yn−1 + 1 < Φ + 1 =⇒ yn = 1 + yn−1 < Φ + 1 = Φ. √ So by induction, yn < Φ. So 1 ≤ yn < Φ gives that yn2 − yn − 1 < 0, or yn < 1 + yn = yn+1 . Thus (yn ) is an increasing sequence that is bounded above, so it converges to some limit, c. We have � � √ c = lim yn = lim 1 + yn−1 = 1 + lim yn−1 = 1 + c. n→∞ n→∞ n→∞ √ So now c = 1 + c which gives c2 = c + 1, and since c > 1, we once again have c = Φ. zn+1 d) Now we define z1 = z2 = 1, and zn = zn−1 + zn−2 for n > 2. Let’s define xn = . So we zn have z2 1 zn+1 zn + zn−1 zn−1 1 x1 = = = 1, and xn = = =1+ =1+ z1 1 zn zn zn xn−1 But this is exactly the same as the (xn ) from a)! Exxxxxcellent... it’s all falling into place. We have shown xn → Φ, so the ratios of consecutive Fibonacci numbers approaches Φ.