Intro Real Analysis, Lec 9: Recursive Sequences, Limit Superior & Inferior Definitions & Properties

(0:00) Exam 1 this week and this lecture will include review.
(3:05) Recursive sequence example (prove it converges and find the limit).
(8:02) Prove the sequence example is bounded above by 6 by mathematical induction.
(10:25) Prove the sequence example is monotone increasing by using the recursive formula and the fact that the sequence is bounded above by 6 (without using induction).
(13:45) This convergent sequence does in fact converge to 6 by using algebraic properties of limits. Be careful: the sequence must be known to converge before you can algebraically solve for the limit (make cobweb plots as well).
(19:51) Definition of the limit superior (limsup) of a sequence and a visual example.
(26:10) Example 1: Relate to the theorem about how, for a bounded sequence, the limit superior is the supremum of the set of all possible subsequential limits of the sequence.
(28:36) Example 2 for this theorem.
(30:16) Example 3 for this theorem.
(31:03) Example 4 for this theorem.
(33:27) Example 5 for this theorem.
(36:54) Some properties of limit superiors and limit inferiors.
(40:05) Review: subsequence and the Bolzano-Weierstrass Theorem.
(42:58) Should understand the proof of Bolzano-Weierstrass, but it will not be on the exam.
(43:41) If a sequence has two subsequences that converge to two different numbers, than the original sequence cannot converge.
(44:15) Monotone convergence theorem (be able to prove), Cauchy sequences, and the Cauchy converge criterion.
(46:12) Definition of convergence. Convergent sequences are bounded. Squeeze theorem. Algebraic properties of limits of sequences.
(49:32) Definition of bounded, monotone, eventually monotone.
(49:58) Back to Chapter 1: increasing/decreasing function, relative maximum/minimum, cardinality of a set, a countable union of countable sets is a countable set, Q is countably infinite, R is uncountable, Completeness axiom, Archimedean property, rationals and irrationals are both dense in the reals, triangle inequality, geometric sums, ordered fields.

Bill Kinney, Bethel University Department of Mathematics and Computer Science. St. Paul, MN.

AMAZON ASSOCIATE
As an Amazon Associate I earn from qualifying purchases.

[nehalamba]

It was little tricky but with some pauses, replays and also brainstorming, I was able to understand it very well. Answers to most of the confusions are present in your words actually. I wonder if only my brain is too slow to process that.
Anyways, thanks for the lecture, Prof. The Concept of Limsup and Liminf is crystal clear now.

[jonaskoelker]

47:03 If you got a sequence in a bounded interval and it converges, it converges to something in that interval.

Theorem: if a_n <= b_n with a_n -> a and b_n -> b then a <= b
Proof: assume a > b and consider this number line ----(near
We can pick some epsilon > 0, for example the average of a and b, such that the open intervals near a and b are disjoint.
For large enough N the a_n all lie near a and the b_n all lie near b (take N = max {N_a, N_b} where the N_a and N_b work for the respective sequences).
But if n >= N then b_n < b + epsilon < a - epsilon < a_n, which contradicts b_n >= a_n.

(Corollary: if a_n -> c and a_n -> d then c = d. Proof: let b_n = a_n and apply the above twice to conclude c <= d and d <= c, implying c = d.)

Now consider a sequence {c_n} with c_n in [x, y]. Assume {c_n} converges.
Clearly the c_n are bounded below and above by the constant sequences x_n = x and y_n = y.
But then x = lim x_n <= lim c_n <= lim y_n = y, i.e. lim c_n in [x, y].

[jonaskoelker]

38:55 "[Why is limsup = liminf when x_n converges]"

Earlier it was stated that limsup = sup L where L = { x | x is a limit of some subsequence of x_n }.
If x_n converges every subsequence has the same limit. Hence L is a singleton set.
Assuming liminf = inf L analogously, it follows that inf {x} = x = sup {x}.

[weilam]

How can I get the pdf verison of Real Analysis, A First Course, 2nd Edition by Russell A. Gordon?

[jonaskoelker]

Here's my basic toolkit for understanding recursive sequences:

1. If x_{n+1} = f(x_n) for some continuous function f, the limit must be a fixed point of f.
2. Having used (1) to guess a limit x, see if the sequence eventually gets ever closer to it: if |x_{n+1} - x| <= c * |x_n - x| for some c in [0, 1) and for all n not less than some N, then x_n goes to x as n goes to infinity.

To apply them, e.g. to Heron's method (x_{n+1} = (1/2)(x + z/x) for a given positive z):
First use (1) to find a fixpoint: if x = (1/2)x + (1/2)z/x then (1/2)x = (1/2)(z/x) so x = z/x implying x^2 = z.
Then use (2) and a lot of elbow grease and tedious but reasonably straightforward algebra to show that the error terms eventually shrink by some constant factor.

It's easy to prove (2) using the tools in my textbook. I leave the proofs as an exercise in using your book as a reference work:
(a) lim x_{n+1} = lim x_n
(b) Let x_n = c^n for some c in [0, 1). Then lim x_n = 0
(c) If a_n < b_n < c_n and lim a_n = lim c_n = x then b_n converges, and lim b_n = x (the squeeze theorem)
(d) If |x_n| -> 0 then x_n -> 0 as n -> infinity
(e) If lim (x_n - x) = 0 then lim x_n = x
Use (a) inductively to ignore all terms before the given N; and by induction |x_{N+k} - x| <= c^k * |x_N - x| so use (b-e).

Proving (1) required an independent thought on my part:
let x_n and f be given, let y_n = x_{n+1} and let z_n = f(x_n).
If x_n converges to x then lim y_n = lim x_n = x and lim z_n = f(lim x_n) = f(x).
But y_n = z_n so the limits are equal; that is, x = f(x).

I understand why one might not yet have taught that continuous functions commute with limits at this point. I wasn't taught this toolkit while we were covering sequences, but it feels like a shame to not have stronger tools than peeling apart algebraic combinations of limits by hand each time. [Yes, of course you do the same algebra on continuous functions and their fixed points, but the class of continuous functions is bigger than "closed under the four operations and oh you have these primitives", even though that smaller class is extremely useful.]

Anyways, this can be used to solve (single-input) linear recursions in general:

Suppose x_{n+1} = f(x) where f(x) = a*x + b for some a and b.
If x_n converges it is to some x such that x = a*x + b, i.e. (1-a)x = b i.e. x = b/(1-a).
For example, 3/(1 - 1/2) = 6 and 3/(1 - 2) = -3.

If x_n = x for some n then x_{n+k} = x_n = x for all positive k since x is a fixed point of f, and the sequence converges.

Otherwise, consider that
x_{n+1} - x =
a*x_n + b - b/(1-a) =
a*x_n + [b*(1-a)/(1-a) - b/(1-a)] =
a*x_n + [b - ba - b]/(1-a) =
a*x_n - ba/(1-a) =
a*[x_n - b/(1-a)] =
a*[x_n - x]

If x_0 = x then the sequence is constant and lim x_n = x_0 = x.
If a = 0 then the sequence is eventually constant (x_n = b for n > 0).
If 0 < |a| < 1 then |x_{n+1} - x| <= |a| * |x_n - x| for all n (choose e.g. N = 0) and lim x_n = x.
If a > 1 and x_0 != x the sequence always diverges since the error terms grow exponentially.

If |a| = 1 and x_0 != x (and thus b/(1-a) is undefined) the sequence either:
diverges to +/- infinity in additive steps of size |b|, if a = 1 and b != 0; or
is constant, if a = 1 and b = 0 and thus f is the identity function; or
oscillates between x_0 and b - x_0, if a = -1. One particularly common pair of examples is |x_0| = 1 and b = 0.

For example, if x_{n+1} = x_n/2 + 3 then a=1/2 and b=3 so the sequence converges to 3/(1 - 1/2) = 6 for all x_0.
Alternatively, if x_{n+1} = 2*x_n + 3 then a=2 an b=3 so the sequence is constant if x_0 = -3 (and thus convergent to -3) and it diverges if x_0 is not -3.

[yesudastare]

fine lecture.
sir.. can u name the book?? please..for refrence that u use in ur class...

[CountDuckula]

What kind of sick individual schedules a maths exam at 07:20 am.

[marciealfaro]

do you have any pdf lecture notes to follow along with your lecture videos?

[akshanshchoudhary]

Sometimes he talks like Harrison Wells from 'The Flash' series :P, Nice video though thanxx