Tutorial week 5 PDF

Preview

Summary

Tutorial week 5...

Description

MAST20026 REAL ANALYSIS

5A

Mathematical Induction and Sequences Important Ideas: 1.

• ǫ-M definition of convergence • Divergence

• Mathematical Induction • Sequences

Mathematical Induction Prove the following theorems using mathematical induction.

2.

(a) ∀n ∈ N,

13 + 23 + 33 + · · · + n3 = 41 n2 (n + 1)2

(b) ∀n ∈ N,

n ≥ 4 =⇒ n2 ≤ n!

Strong induction Imagine that you have an infinite supply of 5 cent and 4 cent postage stamps. We will prove that you can use these stamps to send any amount of postage totaling more than 12 cents by following these steps. (a) First show that you can make 12, 13, 14, and 15 cents of postage directly. (For example 12 cents is 3 × 4 cent stamps) (b) Now let k + 1 ≥ 16 be a number of cents. Assume that for any n ≤ k you can make n cents exactly with your 4 and 5 cent stamps. How can you relate the stamps you should use for k + 1 cents to a the stamps for some lower number n. (c) Use this to show that you can make k + 1 cents using 4 and 5 cents stamps and use Strong Induction to conclude that you can indeed make any number of cents with your stamps. (You can break this into cases: Case 1 being k + 1 ≤ 15, in which case you have checked your p(k + 1) is true already, and the Case 2 being k + 1 ≥ 16.)

3.

Clustering Values Recall that a sequence is a function from N to R, f : N → R. Consider the function f : N → R defined by f (n) = 3n21−2 Find natural numbers M1 , M2 , M3 ∈ N and (for question iv) a function M : N → N such that: (i) f (n) < 10 for all n > M1 . (ii) f (n) <

4.

1 10

(iii) f (n) <

for all n > M2 .

1 100

for all n > M3 .

(iv) f (n) < 10−k for all n > M (k), for k ∈ N.

Guess the Limit Using your intuition and calculus-style arguments, guess whether the following sequences have limits as n goes to infinity. If so, what are the limiting values? Hint: Try graphing the sequence if you get stuck. ( 3 n+1 n2 + 6 nn n ≤ 10100 (a) (c) (−1)n (b) (d) n n+5 3n2 + 4 0 n > 10100

5.

Horsing Around Below is a famous proof by induction that all horses are the same colour. Claim. All horses are the same colour. Proof. Let P (n) be the statement that “within any set of n horses, there is only 1 colour”. • Base case. Consider P (1). Clearly any set with 1 horse only has 1 colour. Therefore P (1) is true. • Induction step. Assume ∃k ∈ Z such that P (k) is true. So, any set of k horses is a single colour. Now consider a set of k + 1 horses. Number the horses h1 , h2 , . . . hk , hk+1.

University of Melbourne

1

Mathematics and Statistics v1.8

Make two new sets of horses: {h1 , h2 , . . . hk } and {h2 , h3 , . . . hk+1}. Both these sets contain k horses, and so contain only 1 colour (by the inductive hypothesis). But the two sets overlap, so within the set {h1 , . . . , hk+1}, there is only one colour. It follows that P (k) =⇒ P (k + 1). It follows that P (n) is true ∀n ∈ N. Therefore, all horses are the same colour.



Of course, it’s not the case that all horses have the same colour... What’s wrong with the proof?

University of Melbourne

2

Mathematics and Statistics v1.8

MAST20026 REAL ANALYSIS

5B

Mathematical Induction and Sequences 6.

A Key Definition (a) Using mathematical notation, define the statement “the limit of fn is L” mathematically. (b) Define the statement “fn converges”. (c) Negate your answer from part (b) to find a mathematical expression for the statement “fn does not converge”. You should have a few quantifiers to negate!

7.

The ǫ-M Definition of Convergence We revisit some of the limits from the A tutorial. Prove the following using ǫ-M techniques: 3 =0 n→∞ n + 5

(a) lim

8.

(b) lim

n→∞

n2 + 6 1 = 2 3 3n + 4

(c) (−1)n

n+1 diverges n

Combining Sequences Consider the sequences an = (3n2 + 1)/n2

bn = (2n − 1)/n

(a) Give an expression for cn = an + bn and guess the limit. Comment on the relationship between this limit and the limits of an and bn . (b) Give an expression for d n = an · bn and guess the limit. Again, comment on the relationship. (c) Find sequences en and fn such that (i) en has a limit, (ii) fn does not have a limit, but (iii) en · fn does have a limit. (d) Find sequences gn , hn such that gn · hn has a limit but neither gn nor hn have limits.

Fascinating Facts In this course, we are focussing on the ǫ − M notion of limit, where a sequence fn may approach a specific real number L as n → ∞. But what if want to say that a sequence fn “approaches” another sequence gn ? For instance, what does it mean for n2 + 4n to approach n2 as n → ∞? One thing we observe is that the ratio (n2 + 4n)/n2 approaches 1 as n gets large. More precisely, lim

n→∞

n2 + 4n = 1. n2

In general, for fn , gn 6= 0, we say fn asymptotical ly approaches gn , and write fn ∼ gn , just in case lim gn /fn = 1.

n→∞

Here are a few examples: • A polynomial of degree d asymptotically approaches its leading term, ad nd + ad−1 nd−1 + · · · + a0 ∼ ad nd . • If an ≪ bn in the asymptotic hierarchy (see the problem sheet), then an + bn ∼ bn . For instance, 2n + n42 ∼ 2n . • Stirling’s approximation: n! ∼ (2πn)1/2

 n n

. e This last approximation is often useful in probability and applied maths. n Challenge: Show that fn ∼ gn iff limn→∞ fnf−g = 0. In words, fn ∼ gn just in case the difference between n the two sequences is much smaller than either sequence as n gets large.

University of Melbourne

3

Mathematics and Statistics v1.8...