Math 104: Introduction to Analysis SOLUTIONS

1 Math 104: Introduction to AnalysisSOLUTIONSA lexander GiventalHOMEWORK that12+ 22+ +n2=16n(n+ 1)(2n+ 1)for alln (n) =n(n+ 1)(2n+ 1)/6. Thenf(1) = 1, the theoremholds true forn= 1. To prove the theorem, it suffices to assume thatit holds true forn=mand derive it forn=m+ 1,m= 1,2,3, ..We havef(m+ 1) f(m) =16(m+ 1)[(2m+ 3)(m+ 2) m(2m+ 1)]=16(m+ 1)(6m+ 6) = (m+ 1) the induction hypothesis,f(m) = mk=1k2, and thereforef(m+ 1) =f(m) + (m+ 1)2=m+1 k= for whichnthe inequality2n> n2holds true, and proveit by mathematical inequality is falsen= 2,3,4, and holds true for all othern , it is true by inspection forn= 1, and the equality 24= 42holds true forn= 4. Thus, to prove the inequality for alln 5, itsuffices to prove the following inductive step:For anyn 4, if 2n n2, then 2n+1>(n+ 1) is not hard to see: 2n+1= 2 2n 2n2, which is greater than(n+1)2provided that (n+1)< whenn >1/( 2 1) = 2+1,which includes all integersn (nk):=n!/k!(n k)!, prove (a)(nk)+(nk 1)=(n+1k)fork= 1.

2 , n, and (b) derive the binomial theorem by induction.(b) Note that1k+1n k+ 1=(n k+ 1) +kk(n k+ 1)=n+ 1k(n k+ 1).Thereforen!k!(n k)!+n!(k 1)!(n k+ 1)!=n!(k 1)!(n k)![1k+1n k+ 1]=n!(k 1)!(n k)![n+ 1k(n k+ 1)]=(n+ 1)!k!(n k+ 1)!.(c) Forn= 1 we have (a+b)n=a+b=(11)a+(11) for somen 1(a+b)n=n k=0(nk)akbn (a+b)n+1= (a+b)n l=0(nl)albn l=n+1 k=0[(nk 1)+(nk)]akbn+1 k=n+1 k=0(n+ 1k)akbn+1 that[3 + 2]2/3does not represent a rational it does represent a rational numberq. Thenq3= [3+ 2]2=9+6 2+2 = 11+6 2. Then 2 = (q3 11)/6 Q, which contradictsirrationality of induction to prove|a1+a2+ +an| |a1|+|a2|+ +|an|fornnumbersa1, a2, .. , Forn= 1, we need|a1| |a1|, which is true Suppose the required inequality is true forn=k. Then forn=k+ 1, using the triangle inequality, we obtain:|a1+ +ak+ak+1| |a1+ +ak|+|ak+1| |a1|+ +|ak|+|ak+1|.Thus the required inequality holds true for anyn= 1,2, .. infima of sets:(a) inf[0,1] = 0(b) inf(0,1) = 0(c) inf[2,7] = 2(d) inf{ , e}=e(e) inf{1n:n N}= 0(f) inf{0}= 0(g) inf[0,1] [2,3] = 0(h) inf n=1= [2n,2n+ 1] = 2(i) inf n=1[ 1n,1 +1n] = 0(j) inf{1 13n:n N}=23(k) inf{n+( 1)nn:n N}= 0 (l) inf{r Q:r <2}= (m) inf{r Q:r2<4}= 2 (n) inf{r Q:r2<2}= 2(o) inf{x R:x <0}= (p) inf{1, 3, 2,10}= 1(q) inf{0,1,2,4,8,16}= 0(r) inf n=1(1 1n,1 +1n) = 1(s) inf{1n:n Nis prime}= 0 (t) inf{x R:x3<8}= (u) inf{x2:x R}= 0(v) inf{cos n3:n N}= 1(w) inf{sin n3:n N}= that givena < b, there exists an irrationalxsuch thata < x < :first show thatr+ 2is irrational whenr the hint, we proveby contradiction (reductio ad absurdum)thatr+ 2 is irrational whenr Q.

3 Indeed, if for a rationalr, thenumberx=r+ 2 were rational, then 2 =x rwould have beenrational, which is , using density ofQinR, find a rationalrsuch thata 2<r < b 2. Thenx=r+ 2 is irrational, and such thata < x < bounded subsetsA, B R, andS={a+b:a A, b B}, prove thatinfS= infA+ anya Aandb B, we have:a infA, b infB,and hencea+b infA+ := infA+ infBis a lower bound prove thatxis the greatest lower bound, let us show that for any >0 we can finds Ssuch thatx s < (which would guaranteethat no lower bound ofSgreater thanxexists). For this, finda Aandb Bsuch that infA a < /2 and infB b < /2. Thens=a+b Swill satisfyx s < , b R. Show that ifa b+1nfor alln N, thena us argue byreductio ad absurdum. Suppose thata > b. Thena b >0, and therefore, by the Archimedian property ofR, thereexistsn Nsuch thata b >1n. For thisn, we have:a > b+1n,which contradicts the thatsn= cos(n /3)does not 1, ..,6 the terms of the sequence are 1/2, 1/2, 1, 1/2,1/2, 1, which then repeat periodically.

4 Thus for any numbers, and anyNone can findn > Nsuch thatsn= 1, hencesn+3= 1, an therefore,by the triangle inequality, either|sn s| 1, or|sn+3 s| thatlim[ 4n2+n 2n] = 1/4. 4n2+n 2n=n 4n2+n+ 2n=12 1 +14n+ any 1< a, we have 1< a < a2, and therefore1 lim 1 +12n lim[1 +12n]= 1 + 0 = other theorems about behavior of limits under arithmeticoperations with sequences, we conclude thatlim12 1 +14n+ 2=12 1 + 2= 1andtn+1= (t2n+ 2)/2tnforn 1. Assume thattnconverges and find the thatt:= limtnexists. Then limtn+1=tas well. Foralln, we have: 2tntn+1=t2n+ 2. Passing to the limit and usingtheorems about limits of sums and products of sequences, we concludethat 2t2=t2+ 2. (In other words, the limittif exists, must be a fixedpoint of the functiontn+1= (t2n+ 2)/2tn, namely:t= (t2+ 2)/2t.) Wefind thereforet= 2. Since the sequencetnwith the initial valuet1= 1 stays positive for alln, the limit has to be + this method of computing 2, we find:t1= 1,t2= 3/2,t3= 17/12, which is already a good approximation, since(17/12)2= 289/144 = allsn6= 0and that the limitL= lim|sn+1/sn| that ifL <1, thenlimsn= thatL < a <1.

5 For =a L >0, there existsNsuchthat for alln Nthe ratiosn+1/sndiffers fromLby no more than ,and hence|sn+1/sn|< L+ =a <1. In particular,|sN+1|< a|sN|,|sN+2|< a|sN+1|< a2|sN|, and so on, by induction,|sN+n|< an|sN|for alln N. We conclude:limn |sn|= limn |sN+n| limn an|sN|=|sN|limn an= 0when|a|< thatlimn ann!= 0for alla ! and find thatsn+1/sn=a/(n+ 1) tends to 0 asn . Therefore, by the previous exercise, limsn= 0. (In otherwords,n! grows faster than any exponential sequencean.)HOMEWORK (a)Let(sn)be a sequence such that|sn+1 sn|<2 nfor alln N. Prove that(sn)is a Cauchy sequence and hence a anym > n, we have|sm sn| n k<m|sk+1 sk|< n k<m2 k= 2 n+1 2 m<2 n+ , for any given >0, choosingNsuch that 2 N+1< , wewill have|sm sn|< for allm n N. Thus (sn) is a Cauchysequence.(b)Is the result (a) true if we only assume that|sn+1 sn|<1/nfor alln N?No. To construct a counter-example, let us prove first that n=11n= .Indeed, for eachk, there are 2k 2k 1 2k= 2k 1numbers of the form1/nbetween 1/(2k 1+ 1) and 1/2k.

6 Each of them is at least as largeas 1/2k, and hence they and up to 2k 1/2k= 1. Thus the sum of thefirstmsuch groups is at leastm/2, n=21n m k=112= the sum of finitely many many terms of the series becomes greaterthan any positive integermwhen the number of the summands , putsn:= nk=11k, so that limsn= , but|sn+1 sn|=1n+ 1<1nfor alln a bounded non-empty subset ofR, and supposesupS / S. Prove that there is a non-decreasing sequence(sn)of pointsinSsuch thatlimsn= eachn N, constructsn Ssuch that supS sn<1/nandsn> sn 1forn >1. Then (sn) will be an increasing sequenceconverging to by pickings1 Ssuch that supS s1<1. This is possiblesince otherwise supS 1<supSis not an upper bound ofS. Proceedby induction: suppose thats1< .. < sn 1with required propertieshave been found. Since supS / S, we havesn 1<supS. Thereforethere existssn Ssuch thatsupS sn> sn 1and supS sn<1/n,which is possible since neithersn 1<supSnor supS 1/n <supSis an upper bound (sn)and(tn)be the following two sequences that repeat incycles of four:(sn) = (0,1,2,1,0,1,2,1.)

7 ,(tn) = (2,1,1,0,2,1,1,0, ..).Then:(a) lim infsn+ lim inftn= 0 + 0 = 0,(b) lim inf(sn+tn) = 1,(c) lim infsm+ lim suptn= 0 + 2 = 2,(d) lim sup(sn+tn) = 3,(e) lim supsn+ lim suptn= 2 + 2 = 4,(f) lim infsntn= 0,(e) lim supsntn= the semiperimeter of a regular3x2n- gon( ,6-gon,12-gon,24-gon, etc.) inscribed into a circle ofradius1. Prove that the sequencepnconverges, and that the limit(commonly called ) is greater the number of sides of a regular polygon doubles,each side of them-gon is replaced by a broken line consisting of twoadjacent sides of the 2m-gon connecting the same endpoints. Since, bythe triangle inequality, a broken line is longer than the straight segmentconnecting the same endpoints, we conclude that the sequencepnofsemiperimeters is increasing. It is easy to see from elementary geometrythat the side of a regular hexagon inscribed into a unit circle has length1, and thereforep1= 3. Thus, it suffices to show that the sequencepnisbounded above, to conclude that the limit exists and is greater than fact it is not hard to show that the perimeter of anyconvexpolygondoes not exceed the perimeter of any polygon containing it.

8 To seethis, go around the convex polygon clockwise and extend eachside ofit forward up to its first intersection with the boundary of the enclosingpolygon. Then write down the triangle inequality estimating aboveeach of the extended sides by the length of the broken line connectingits endpoints and consisting of the extending segment of thepreviousside, and a part of the perimeter of the enclosing polygon. Summingup all these inequalities, we obtain the required inequality between theperimeters of the enclosed and enclosing polygons (since the extendingsegments occur on both sides of the inequality and thus cancel out).This implies that eachpnis smaller than the semiperimeter of anypolygon enclosing the unit disk, ( the square of size 2 2, whosesemiperimeter equals 4). In particular, we conclude that < set is called closed if it contains all its subsequentiallimits (see p. 72). A set is called open if its complement is that a set is open if and only if together with any point,it containssome open interval containing this thatx Sis not contained inStogether with any openinterval.

9 Then for anyn Nthere existsxn/ Ssuch that|xn x|>1/n. The sequence (xn) is in the complement ofSand converges tox, which is not in the complement. Thus the complement ofSis versa, suppose the complement ofSis not closed, thereexists a sequence (xn) in the complement ofSwhich converges tox any open interval containingxwill contain some elements of thesequence (xn) and thus will not lie there a sequence(sn)such that(0,1)is its set of subse-quential limits?No, the set of subsequential limits of any set must be closed,but theinterval (0,1) (not including its endpoints) is not that(sn)is bounded if and only iflim sup|sn|<+ .If lim supsn= + , then there exists a subsequence (snk) such thatlim|snk|= + , and therefore this subsequence is , if (sn) is unbounded, then for anyk Nthere existssnksuchthat|snk|> k. We may assume thatn1< n2< .. < nk< .., and thusget a subsequence (snk) such that lim|snk|= + , lim sup|sn|=+ . if the series [ n+ 1 n] sums of the series are 2 1+ 3 2+.

10 + n n 1+ n+ 1 n= n+ 1 1,and form a sequence that tends to + . Thus the series a series anwhich diverges by the Root Test, but forwhich the Ratio Test gives no the series an:= 2( 1)nn. Applying the Root Testwe get the sequence|an|1/n= 2( 1)nwhich consists of two constantsubsequences 2 and 1/2, and therefore has lim sup|an|1/n= 2> the series diverges. Applying the Root Test we get the sequence|an/an 1|= 2( 1)n(2n 1)which consists of two subsequences: 22n 1forevenn, and 1/22n 1for oddn, converging respectively to + and to0. Thuslim inf|an/an 1|= 0<1<+ = lim sup|an/an 1|, the Ratio Test is 6(a) n 11 n(n+ 1)converges by the comparison test: 1/n(n+ 1)<1/n2for alln N.(b) n 1(n!)2(2n)!converges by the ratio test: lim|an/an 1|= limn2/2n(2n 1) = 1/4<1.(c) n 1n!nnconverges by the ratio test: lim|an+1/an|= lim(1 + 1/n) n=e 1<1.(d) n 1(n!)22n2converges by the ratio test: lim|an/an 1|= limn2/22n 1= 0<1.(e)10001+1000 10011 3+1000 1001 10021 3 5+ converges by the ratio test: lim|an/an 1|= lim(1000 +n)/(2n+ 1) =1/2<1.