[PDF] let l(d is a dfa that accepts sr whenever it accepts s show that l is turing decidable)
[PDF] let us java pdf
[PDF] let x1 1 and xn+1=2 1/xn
[PDF] let x1=1 and xn+1=3xn^2
[PDF] let xn be a sequence such that there exists a 0 c 1 such that
[PDF] letra cancion bandolero paris latino
[PDF] letter and sound assessment form
[PDF] letter coding examples
[PDF] letter coding tricks
[PDF] letter granting permission to use copyrighted music
[PDF] letter identification assessment free
[PDF] letter identification assessment pdf
[PDF] letter of acceptance of appointment as director
[PDF] letter of appointment of additional director in private company
[PDF] letter of consent for child to travel with grandparents
32 MATH 3333{INTERMEDIATE ANALYSIS{BLECHER NOTES
4.Sequences
4.1.Convergent sequences.
A sequence (sn) converges to a real numbersif8 >0,9Ns:t:jsnsj<
8nN. Saying thatjsnsj< is the same as saying thats < sn< s+.
If (sn) converges tosthen we say thatsis thelimitof (sn) and write s= limnsn, ors= limn!1sn, orsn!sasn! 1, or simplysn!s. If (sn) does not converge to any real number then we say that itdiverges. A sequence (sn) is calledboundedif the setfsn:n2Ngis a bounded set. That is, there are numbersmandMsuch thatmsnMfor alln2N. This is the same as saying thatfsn:n2Ng [m;M]. It is easy to see that this is equivalent to: there exists a numberK0 such thatjsnj K for alln2N. (See the rst lines of the last Section.)
Fact 1.Any convergent sequence is bounded.
Proof:Suppose thatsn!sasn! 1. Taking= 1 in the denition of convergence gives that there exists a numberN2Nsuch thatjsnsj<1 whenever nN. Thus jsnj=jsns+sj jsnsj+jsj<1 +jsj whenevernN. Now letM= maxfjs1j;js2j;;jsNj;1+jsjg. We havejsnj M ifn= 1;2;;N, andjsnj MifnN. So (sn) is bounded. A sequence (an) is callednonnegativeifan0 for alln2N. To say that a nonnegative sequence converges to zero is simply to say that:
8 >0;9Ns:t: an< 8nN:
Fact 2.If (sn) is a general sequence then:
lim nsn=s()limn(sns) = 0()limnjsnsj= 0: That is, the sequence (sn) converges tosif and only if the nonnegative sequence (jsnsj) converges to 0. Fact 3.If (an) and (bn) are nonnegative sequences, with limnan= 0 and lim nbn= 0, and ifC0, then lim nan+bn= limnCan= 0:
Also, if lim
nan= 0 and if (bn) is any bounded sequence, then limnanbn= 0. Fact 4.If (sn) and (tn) are sequences withsntnfor everyn1. If lim nsn=sand limntn=t, thenst. Fact 5: The `squeezing' or `pinching rule'.Suppose that (sn);(xn), and (tn) are sequences withsnxntn, for everyn1. If limnsn=sand lim ntn=s, then limnxn=s.
MATH 3333{INTERMEDIATE ANALYSIS{BLECHER NOTES 33
Fact 6, sometimes call 'squeezing' too,since it is a corollary of Fact 5: Let (sn) be a sequence, letsbe a number, and suppose thatjsnsj anfor alln1, where (an) is a sequence with limit 0. Then limnsn=s. Proof:We have 0 jsnsj an. Nowan!0 asn! 1, so by `squeezing' (Fact 5), lim njsnsj= 0. By Fact 2, limnsn=s. Fact 7:The limit of a sequence has nothing to do with its rst few terms. Fact 8:If limntn=t, and ift6= 0, then there exists a numberNwithjtnj>jtj2 for allnN.
Fact 9:If limnsn=sand limntn=t, then:
(1) lim nsn+tn=s+t; (2) lim nsntn=st; (3) lim nsntn=st; (4) lim nCsn=Cs, ifCis a constant; (5) lim nsnt n=st , ift6= 0; (6) lim njsnj=jsj; (7) lim npt n=pt, iftn0 for alln2N. Proof:By Fact 2, we havejsnsj !0;andjtntj !0, asn! 1. To prove (1), by Fact 6 it is enough to show thatj(sn+tn)(s+t)j an, wherean!0 as n! 1. But j(sn+tn)(s+t)j=j(sns) + (tnt)j jsnsj+jtntj !0; using the triangle inequality, and Fact 3 in the very last step. So we have proved (1). The proof of (3) is similar, by Fact 6, it is enough to show thatjsntnstj an, wherean!0, asn! 1. But jsntnstj=jsntnsnt+sntstj jsntnsntj+jsntstj=jsn(tnt)j+jt(sns)j=jsnjjtntj+jtjjsnsj: Nowjsnsj !0, sojtjjsnsj !0, asn! 1, by Fact 3. On the other hand, since (sn) is convergent, it is bounded, by Fact 1. Thus (jsnj) is bounded. By the nal assertion of Fact 3,jsnjjtntj !0 asn! 1. By the rst assertion of Fact
3, we now see thatjsnjjtntj+jtjjsnsj !0 asn! 1. Sincejsntnstj
jsnjjtntj+jtjjsnsj, by Fact 6 we deduce thatsntn!stasn! 1. So we have proved (3). (4) follows from (3), if we settn=Cfor alln. Applying (4) withC=1 shows that lim n(tn) =t. Using this with (1), gives lim n(sntn) = limn(sn+ (tn)) = limnsn+ limn(tn) =st:
This proves (2).
34 MATH 3333{INTERMEDIATE ANALYSIS{BLECHER NOTES
For (5), we use a similar strategy to (1) and (3). Note that s nt nst =s nttnst nt
By Fact 8,9Ns.t.jtnj>jtj=2 fornN. Thus fornN,s
nt nst Sincejsnsj !0 andjttnj !0, asn! 1, by Fact 3 it follows thatjsn sjjtj+jsjjttnj !0 too. By Fact 3 again,2jtj2(jsnsjjtj+jsjjttnj)!0 as n! 1. Thus we conclude from Fact 6 (in conjunction with Fact 7), thatsnt n!st asn! 1. (6) follows by squeezing too, since we have using Theorem 3.3 (f) above, that jjsnj jsjj jsnsj !0:So by Fact 6,jsnj ! jsj. We omit (7). Innite limits.If (sn) is a sequence, then we write limnsn= +1if8M >
0;9Ns.t.sn> M8nN. We write limnsn=1if8M >0;9Ns.t.
s n
0;8n). Then lim nsn= +1 ,limn1s n= 0: Theorem 4.3.IfSis a nonempty set inRthen
(a)x2Si there is a sequence(sn)inSwith limitx. (b)x2S0i there is a sequence(sn)inSn fxgwith limitx. (c)Sis closed i whenever(sn)is a sequence inSwith limitx, thenx2S. Proof.(a) (() If (sn) is a sequence inSwith limitx, and if >0 is given, then there exists anNwithjsnxj< ifnN. HencesN2N(x;), and soN(x;) contains a point ofS. Thusx2Sby Lemma 3.20. ()) Ifx2S, andn2N, then by Lemma 3.20,N(x;1n ) contains a point of S. Call this pointsn. Sincejsnxj<1=n!0, it follows by Fact 6 in 4.1 that s n!x. (c) (() Suppose that the condition in (c) about sequences holds. Letx2S. By (a), there is a sequencesn!xwithsn2Sfor alln2N. By hypothesis,x2S. So SS, thereforeS=S, and soSis closed by Corollary 3.24. ()) Suppose thatSis closed, and that (sn) is a sequence inSwithsn!x. By (a), we havex2S=S(using Corollary 3.24).
MATH 3333{INTERMEDIATE ANALYSIS{BLECHER NOTES 35
4.2.Monotone sequences and Cauchy sequences.Recall from Calculus II
that a sequence (sn) isincreasingifsnsn+1;8n2N. A sequence (sn) isde- creasingifsnsn+1;8n2N. We saystrictly increasing(resp.strictly decreasing) if thehere (resp.ge) is replaced by<(resp.>). A sequence (sn) ismonotoneif it is increasing or decreasing (or both, which happens for constant sequences). Theorem 4.4.A monotone sequence is convergent i it is bounded. Proof.()) Every convergent sequence is bounded (by Fact 1). (() Suppose that (sn) is a bounded increasing sequence (the decreasing case is similar). LetS=fsn:n2Ng. This is bounded above, and lets= supS. Claim: lim nsn=s. Let >0 be given. Thensis not an upper bound forS. Thus 9Ns.t.sN> s. Hence
s < sNsns < s+ for allnN. We've shown that8 >09Ns.t.jsnsj< for allnN. Thus, the sequence (sn) converges tos. Remark.The last proof shows that a bounded increasing (resp. decreasing) sequenc converges to its supremum (resp. inmum). Proposition 4.5.If(sn)is an unbounded increasing (resp. decreasing) sequence, thenlimnsn= +1(resp.=1). Denition:A sequence (sn) of real numbers is called aCauchy sequenceif 8 >09N2Ns.t.jsnsmj< ;whenevermnN.
Lemma 4.6.Every convergent sequence is a Cauchy sequence. Lemma 4.7.Every Cauchy sequence is bounded.
Theorem 4.8.(Cauchy test for convergence)A sequence inRis convergent i it is a Cauchy sequence. 4.3.Subsequences.Asubsequenceof a sequence (sn) is constructed from (sn) by
removing terms in the sequence. Associated with each subsequence is a strictly increasing sequence of natural numbers (nk)1k=1, namely the place numbers of the terms that were kept from the original sequence to make the subsequence. Summarizing: A subsequence of a sequence (sn)1n=1is a new sequence (tk)1k=1, wheretk=snkfor allk, and wheren1< n2< n336 MATH 3333{INTERMEDIATE ANALYSIS{BLECHER NOTES To say that a subsequence (snk)1k=1converges to a numbers, means that 8 >0;9K >0s:t:jsnksj< 8kK:
Proposition 4.10.If a sequence(sn)converges to a numbers, then every subse- quence(snk)also converges tos. Proof.Given >09Ns.t.jsnsj< 8nN. IfkNthen by Lemma 4.9, we havenkkN, and sojsnksj< . That is,snk!s. Theorem 4.11.(Bolzano-Weierstrass for sequences)Every bounded sequence has a convergent subsequence. Theorem 4.12.Every unbounded sequence contains a monotone subsequence with limit+1or1. Theorem 4.13.A nonempty setSof real numbers is compact i every sequence inShas a convergent subsequence with a limit inS. The limsup and liminf
Denition.Thelimit superiorof a sequence (sn), is the number limsup nsn= limn!1fsupfsk:kngg: Thelimit inferioris
liminf nsn= limn!1finffsk:kngg: What the limsup and liminf are good for:First, they always exist, unlike the limit. For example, in the Example above, lim nsndoes not exist. But we were able to compute the limsup and liminf. They always exist because as we saw in the example, they are limits of monotone sequences, which we know always exist. They behave similarly to the limit. That is, they obey laws analogous to the rules we saw in Section 4.1 above for limits. We will write down some of these laws momentarily. They can be used to check if the limit exists. In fact lim nsnexists i liminf nsn= limsupnsn. So if liminfnsn6= limsupnsnthen we may conclude that lim nsndoes not exist. Finally, recall that in Calculus II there were certain tests ... One can improve these tests by using the limsup and liminf instead of the limit... . Other properties of the limsup and liminf:
In general, liminfnsnlimsupnsn. If limnsnexists then liminfnsn= lim nsn= limsupnsn. liminfn(sn) =limsupnsn. Ifsntnfor allnthen limsupnsnlimsupntnand liminfnsnliminfntn. MATH 3333{INTERMEDIATE ANALYSIS{BLECHER NOTES 37
limsupn(Ksn) =Klimsupnsnand liminfn(Ksn) =Kliminfnsn, ifK0. Summary: any sequence (sn) has a limsup and a liminf (either a real number or 1), which behave like limits.
5.Limits and continuity of functions
5.1.Limits of functions.In this sectionf:D!Ris a function with domain
DR, and letcbe an accumulation point ofD. We recall from Calculus I: Denition:limx!cf(x) =Lif8 >09 >0 s.t.jf(x)Lj< wheneverx2D and 08 >09 >0 s.t.jf(x)Lj< wheneverx2Dandjxcj< . Theorem 5.1.(Main theorem # 1/MT # 1/Main theorem on limits) limx!cf(x) = Li wheneverxn!c;andxn6=cfor alln2N, thenf(xn)!L. Here(xn)is any sequence in the domain off. Proof.()) Suppose that limx!cf(x) =L, and thatxn!c;xn6=cfor alln2N. So given >0 there exists a >0 such thatjf(x)Lj< whenever 00 such that for all >0 there existsxwith 0