Shawn Zhong

Shawn Zhong

 钟万祥
  • Tutorials
  • Mathematics
    • Math 240
    • Math 375
    • Math 431
    • Math 514
    • Math 521
    • Math 541
    • Math 632
    • Abstract Algebra
    • Linear Algebra
    • Category Theory
  • Computer Sciences
    • CS/ECE 252
    • CS/ECE 352
    • Learn Haskell
  • AP Notes
    • AP Microecon
    • AP Macroecon
    • AP Statistics
    • AP Chemistry
    • AP Physics E&M
    • AP Physics Mech
    • CLEP Psycho

Shawn Zhong

 钟万祥
  • Tutorials
  • Mathematics
    • Math 240
    • Math 375
    • Math 431
    • Math 514
    • Math 521
    • Math 541
    • Math 632
    • Abstract Algebra
    • Linear Algebra
    • Category Theory
  • Computer Sciences
    • CS/ECE 252
    • CS/ECE 352
    • Learn Haskell
  • AP Notes
    • AP Microecon
    • AP Macroecon
    • AP Statistics
    • AP Chemistry
    • AP Physics E&M
    • AP Physics Mech
    • CLEP Psycho

Home / 2018 / April / Page 7

Math 521 – 3/23

  • Apr 03, 2018
  • Shawn
  • Math 521
  • No comments yet
Sequences Approaching Infinity • Let {s_n } be a sequence of real numbers s.t. • ∀M∈R,∃N∈N s.t. s_n≥M,∀n≥N • Then we write s_n→+∞ • Similarly if ∀M∈R,∃N∈N s.t. s_n≤M,∀n≥N • Then we write s_n→−∞ Upper and Lower Limits • Definition ○ Let {s_n } be a sequence of real numbers ○ Let E be the set of x (in the extended real number system) s.t. ○ s_(n_k )→x for some subsequence {s_(n_k ) } ○ E contains all subsequential limits of {s_n } plus possibly +∞,−∞ ○ (lim⁡sup)_(n→∞)⁡〖s_n 〗=s^∗=sup⁡E is called the upper limit of {s_n } ○ (lim⁡inf)_(n→∞)⁡〖s_n 〗=s_∗=inf⁡E is called the lower limit of {s_n } • Example 1 ○ s_n=(−1)^n/(1+1/n)={−1/2,2/3,−3/4,4/5,−5/6,…} ○ (lim⁡sup)_(n→∞)⁡〖s_n 〗=sup⁡{−1,1}=1 ○ (lim⁡inf)_(n→∞)⁡〖s_n 〗=inf⁡{−1,1}=−1 • Example 2 ○ lim_(n→∞)⁡〖s_n 〗=s⇒(lim⁡sup)_(n→∞)⁡〖s_n 〗=(lim⁡inf)_(n→∞)⁡〖s_n 〗=s § All subsequential limits of a convergent sequence § converge to the same value as the sequence ○ (lim⁡sup)_(n→∞)⁡〖s_n 〗=(lim⁡inf)_(n→∞)⁡〖s_n 〗=s⇒lim_(n→∞)⁡〖s_n 〗=s § ⇒sup⁡E=inf⁡E § ⇒E={s} § ⇒ All subsequential limits = s § ⇒lim_(n→∞)⁡〖s_n 〗=s Theorem 3.17 • Let {s_n } be a sequence of real numbers, then • s^∗∈E ○ When s^∗=+∞ § E is not bounded above, so {s_n } is not bounded above § There is a subseqnence {〖s_n〗_k } s.t. 〖s_n〗_k→∞ § So s^∗=+∞∈E ○ When s^∗∈R § E is bounded above § And at least one subsequential limit exists i.e. E≠∅ § By Theorem 3.7, E is closed i.e. E=E ̅ § By Theorem 2.28, s^∗=sup⁡E∈E ̅ § Therefore s^∗∈E ○ When s^∗=−∞ § Then E={−∞} § s_n→−∞ and s^∗=−∞∈E • If x s^∗,then ∃N∈N s.t.s_n x for n≥N ○ If ∃x s^∗ with s_n≥x for infinitely many n∈N ○ Then ∃y∈E s.t. y≥x s^∗ ○ This contradicts the definition of s^∗ • Moreover s^∗ is the only number with these properties ○ Suppose p,q∈E,p≠q s.t. the property above holds for p,q ○ Without loss of generality, suppose p q ○ Choose x s.t. p x q ○ Since p satisfies the property above ○ ∃N∈N s.t. s_n x,∀n≥N ○ So no subsequence of {s_n } can converge to q ○ This contradicts the existence of q ○ Therefore only one number can have these properties
Read More >>

Math 521 – 3/21

  • Apr 03, 2018
  • Shawn
  • Math 521
  • No comments yet
Theorem 3.11 • Statement (a) ○ In any metric space X, every convergent sequence is a Cauchy sequence • Proof (a) ○ Suppose p_n→p ○ Let ε 0,then ∃N∈N s.t. d(p,p_n ) ε/2, ∀n≥N ○ d(p_n,p_m )≤d(p,p_n )+d(p,p_m ) ε/2+ε/2=ε, ∀n,m≥N ○ So {p_n } is a Cauchy sequence • Statement (b) ○ If X is a compact metric space and {p_n } is a Cahchy sequence ○ Then {p_n } converges to some point of X • Proof (b) ○ Let {p_n } be a Cauchy sequenec in compact metric space X ○ For N∈N, let E_N={p_N,p_(N+1),…} ○ By Theorem 3.10,lim_(N→∞)⁡〖diam (E_N ) ̅ 〗=lim_(N→∞)⁡〖diam E_N 〗=0 ○ By Theorem 2.35, (E_N ) ̅ as closed subset of X is compact ○ Since E_(N+1)⊂E_N, (E_(N+1) ) ̅⊂(E_N ) ̅,∀N∈N ○ By Theorem 3.10 (b), ∃!p∈X s.t. p∈(E_N ) ̅, ∀N∈N ○ Let ε 0 be given,∃N_0∈N s.t. diam (E_N ) ̅ ε,∀N≥N_0 ○ Since p∈(E_N ) ̅,d(p,q) ε,∀q∈E_N={p_N,p_(N+1),…}⊂(E_N ) ̅ ○ In other word, d(p,p_n ) ε for n≥N_0 ○ So lim_(n→∞)⁡〖p_n 〗=p • Statement (c) ○ In Rk, every Cauchy sequence converges • Proof (c) ○ Let {(x_n ) ⃗ } be a Cauchy sequence in Rk ○ Let E_N={(x_N ) ⃗,(x_(N+1) ) ⃗,…} ○ For some N∈N,diam E_N 1 ○ Then the range of {(x_n ) ⃗ } is {(x_1 ) ⃗,…,(x_(N−1) ) ⃗ }∪E_N ○ By Theorem 2.41, every bounded subset of Rk has compact closure in Rk ○ (c) follows from (b) Complete Metric Space • Definition ○ A metric space X is said to be complete if ○ every Cauchy sequence converges in X • Examples ○ Rk is complete ○ Compact metric space X is complete ○ Q is not complete (convergence may lie outside of Q) Monotonic Sequence • A sequence {s_n } of real numbers is said to be • monotonically increasing if s_n≤s_(n+1), ∀n∈N • monotonically decreasing if s_n≥s_(n+1), ∀n∈N • monotonic if {s_n } is either monotonically increasing or decreasing Theorem 3.14 (Monotone Convergence Theorem) • Statement ○ If {s_n } is monotonic, then {s_n } converges if and only if it is bounded • Proof ○ By Theorem 3.2 (c), converge implies boundedness ○ Without loss of generality, suppose {s_n } is monotonically increasing ○ Let E=range {s_n }, and s=sup⁡E, then s_n≤s,∀n∈N ○ Given ε 0,∃N∈N s.t. s−ε s_n≤s,∀n≥N ○ Since s−ε is not an upper bound of E, and {s_n } is increasing ○ s−s_n ε,∀n≥N⇒lim_(n→∞)⁡〖s_n 〗=s
Read More >>

6.2 The Pigeonhole Principle

  • Apr 02, 2018
  • Shawn
  • Math 240
  • No comments yet
The Pigeonhole Principle • Introduction ○ If a flock of 20 pigeons roosts in a set of 19 pigeonholes ○ Then, one of the pigeonholes must have more than 1 pigeon. • Pigeonhole Principle ○ If k is a positive integer and k + 1 objects are placed into k boxes ○ Then at least one box contains two or more objects. • Proof ○ We use a proof by contraposition. ○ Suppose none of the k boxes has more than one object ○ Then the total number of objects would be at most k. ○ This contradicts the statement that we have k + 1 objects. • Corollary 1 ○ A function f from a set with k + 1 elements to a set with k elements is not one-to-one. • Proof ○ Use the pigeonhole principle. ○ Create a box for each element y in the codomain of f . ○ Put in the box for y all of the elements x from the domain such that f(x)=y. ○ Because there are k + 1 elements and only k boxes, at least one box has two or more elements. ○ Hence, f can’t be one-to-one. • Example ○ Among any group of 367 people, there must be at least two with the same birthday ○ Because there are only 366 possible birthdays. • Example ○ Show that for every integer n there is a multiple of n that has only 0s and 1s in its decimal expansion. ○ Let n be a positive integer. ○ Consider the n + 1 integers 1, 11, 111, … , 11…1 (where the last has n + 1 1s). ○ There are n possible remainders when an integer is divided by n. ○ By the pigeonhole principle, when each of the n + 1 integers is divided by n, at least two must have the same remainder. ○ Subtract the smaller from the larger and the result is a multiple of n that has only 0s and 1s in its decimal expansion. The Generalized Pigeonhole Principle • The Generalized Pigeonhole Principle ○ If N objects are placed into k boxes ○ Then there is at least one box containing at least ⌈N/k⌉ objects. • Proof ○ We use a proof by contraposition. ○ Suppose that none of the boxes contains more than ⌈N/k⌉−1 objects. ○ Then the total number of objects is at most ○ k(⌈N/k⌉−1) k((⌈N/k⌉+1)−1)=N ○ where the inequality ⌈N/k⌉ ⌈N/k⌉+1 has been used. ○ This is a contradiction because there are a total of n objects. • Example ○ Among 100 people there are at least ⌈100/12⌉ = 9 who were born in the same month. • Example ○ How many cards must be selected from a standard deck of 52 cards to guarantee that at least three cards of the same suit are chosen? ○ We assume four boxes; one for each suit. ○ Using the generalized pigeonhole principle, at least one box contains at least ⌈N/4⌉ cards. ○ At least three cards of one suit are selected if ⌈N/4⌉ ≥3. ○ The smallest integer N such that ⌈N/4⌉ ≥3 is N = 2 ∙ 4 + 1 = 9. • Example ○ How many must be selected to guarantee that at least three hearts are selected? ○ A deck contains 13 hearts and 39 cards which are not hearts. ○ If we select 41 cards, we may have 39 cards which are not hearts along with 2 hearts. ○ However, when we select 42 cards, we must have at least three hearts. ○ (Note that the generalized pigeonhole principle is not used here.)
Read More >>

6.1 The Basics of Counting

  • Apr 02, 2018
  • Shawn
  • Math 240
  • No comments yet
Basic Counting Principles: The Product Rule • The Product Rule ○ A procedure can be broken down into a sequence of two tasks. ○ There are n_1 ways to do the first task and n_2 ways to do the second task. ○ Then there are n_1∙n_2 ways to do the procedure. • Example 1 ○ How many bit strings of length seven are there? ○ Since each of the seven bits is either a 0 or a 1, the answer is 2^7 = 128. • Example 2 ○ How many different license plates can be made if ○ each plate contains a sequence of 3 uppercase English letters followed by 3 digits? ○ There are 26 ∙ 26 ∙ 26 ∙ 10 ∙ 10 ∙ 10 = 17,576,000 different possible license plates. • Example 3: Counting Functions ○ How many functions are there from a set with m elements to a set with n elements? ○ A function represents a choice of one of the n elements of the codomain for each of the m elements in the domain ○ The product rule tells us that there are n⋅n⋯n = n^m such functions. • Example 4: Counting One-to-One Functions ○ How many 1-to-1 functions are there from a set with m elements to one with n elements? ○ Suppose the elements in the domain are a_1,a_2,…,a_m. ○ There are n ways to choose the value of a_1 and n−1 ways to choose a_2, etc. ○ The product rule tells us that there are n(n−1)(n−2)⋯(n−m+1) functions. • Example 5: Counting Subsets of a Finite Set ○ Show that the number of different subsets of a finite set S is 2^|S| ○ When the elements of S are listed in an arbitrary order ○ There is a one-to-one correspondence between subsets of S and bit strings of length |S|. ○ When the ith element is in the subset, the bit string has a 1 in the ith position and a 0 otherwise. ○ By the product rule, there are 2^|S| such bit strings, and therefore 2^|S| subsets. • Example 6: Product Rule in Terms of Sets ○ Let A_1,A_2,…,A_m be finite sets ○ The number of elements in the Cartesian product of these sets is the product of the number of elements of each set. ○ The task of choosing an element in the Cartesian product A_1×A_2×…×A_m is done by ○ choosing an element in A_1, an element in A_2 , …, and an element in A_m. ○ By the product rule, it follows that: |A_1×A_2×…×A_m |=|A_1 |⋅|A_2 |⋯|A_m | • Example 7: DNA and Genomes ○ A gene is a segment of a DNA molecule that encodes a particular protein and the entirety of genetic information of an organism is called its genome. ○ DNA molecules consist of two strands of blocks known as nucleotides. ○ Each nucleotide is composed of bases: adenine(A), cytosine(C), guanine(G), thymine(T). ○ The DNA of bacteria has between 〖10〗^5 and 〖10〗^7 links (one of the four bases). ○ Mammals have between 〖10〗^8 and 〖10〗^10 links. ○ So, by the product rule there are at least 4^(〖10〗^5 ) different sequences of bases in the DNA of bacteria and 4^(〖10〗^8 ) different sequences of bases in the DNA of mammals. ○ The human genome includes approximately 23,000 genes, each with 1,000 or more links. Basic Counting Principles: The Sum Rule • The Sum Rule ○ If a task can be done either in one of n_1 ways or in one of n_2, ○ where none of the set of n_1 ways is the same as any of the n_2 ways, ○ then there are n_1+n_2 ways to do the task. • Example ○ The mathematics department must choose either a student or a faculty member as a representative for a university committee. ○ How many choices are there for this representative if there are 37 members of the mathematics faculty and 83 mathematics majors and no one is both a faculty member and a student. ○ There are 37 + 83 = 120 possible ways to pick a representative. • The Sum Rule in terms of sets ○ The sum rule can be phrased in terms of sets. ○ |A ∪ B|= |A| + |B| as long as A and B are disjoint sets. ○ Or more generally, § |A_1∪A_2∪…∪A_m |=|A_1 |+|A_2 |+…+|A_m |, when A_i∩A_j=∅ for all i,j Combining the Sum and Product Rule • Example 1 ○ Suppose statement labels in a programming language can be either a single letter or a letter followed by a digit. ○ Find the number of possible labels. ○ Use the product rule: 26 + 26 ∙ 10 = 286 • Example 2: Counting Passwords ○ Each user on a computer system has a password ○ which is 6 to 8 characters long, where each character is an uppercase letter or a digit. ○ Each password must contain at least one digit. ○ How many possible passwords are there? ○ Let P be the total number of passwords ○ Let P_6, P_7, and P_8 be the passwords of length 6, 7, and 8. ○ By the sum rule P=P_6+P_7+P_8. ○ To find each of P_6, P_7, and P_8, we find the number of passwords of the specified length composed of letters and digits and subtract the number composed only of letters. ○ We find that: § P_6 = 〖36〗^6 − 〖26〗^6 = 2,176,782,336 − 308,915,776 =1,867,866,560 § P_7 = 〖36〗^7 − 〖26〗^7 = 78,364,164,096 − 8,031,810,176 = 70,332,353,920 § P_8 = 〖36〗^8 − 〖26〗^8 = 2,821,109,907,456 − 208,827,064,576 = 2,612,282,842,880 ○ Consequently, P=P_6+P_7+P_8 = 2,684,483,063,360. Basic Counting Principles: Subtraction Rule • The Subtraction Rule ○ If a task can be done either in one of n_1 ways or in one of n_2 ways ○ Then the total number of ways to do the task is n_1 + n_2 minus the number of ways to do the task that are common to the two different ways. ○ Also known as, the principle of inclusion-exclusion: ○ |A∪B|=|A|+|B|−|A∩B| • Example: Counting Bit Strings ○ How many bit strings of length eight either start with a 1 bit or end with the two bits 00? ○ Use the subtraction rule. ○ Number of bit strings of length eight that start with a 1 bit: 2^7 = 128 ○ Number of bit strings of length eight that end with bits 00: 2^6 = 64 ○ Number of bit strings of length eight that start with a 1 bit and end with bits 00: 2^5 = 32 ○ Hence, the number is 128 + 64 − 32 = 160. Basic Counting Principles: Division Rule • Division Rule ○ There are n/d ways to do a task if ○ it can be done using a procedure that can be carried out in n ways ○ and for every way w, exactly d of the n ways correspond to way w. • In terms of sets ○ If the finite set A is the union of n pairwise disjoint subsets each with d elements ○ then n = |A|/d. • In terms of functions ○ If f is a function from A to B, where both are finite sets, and for every value y ∈ B there are exactly d values x ∈ A such that f(x)=y, then |B|=|A|/d. • Example ○ How many ways are there to seat four people around a circular table, where two seatings are considered the same when each person has the same left and right neighbor? ○ Number the seats around the table from 1 to 4 proceeding clockwise. ○ There are four ways to select the person for seat 1, 3 for seat 2, 2, for seat 3, and one way for seat 4. ○ Thus there are 4! = 24 ways to order the four people. ○ But since two seatings are the same when each person has the same left and right neighbor, for every choice for seat 1, we get the same seating. ○ Therefore, by the division rule, there are 24/4 = 6 different seating arrangements. Tree Diagrams • Tree Diagrams ○ We can solve many counting problems through the use of tree diagrams, where a branch represents a possible choice and the leaves represent possible outcomes. • Example ○ Suppose that “I Love Discrete Math” T-shirts come in five different sizes: S, M, L, XL, XXL. ○ Each size comes in four colors (white, red, green, and black), except XL, which comes only in red, green, and black, and XXL, which comes only in green and black. ○ What is the minimum number of shirts that the campus book store needs to stock to have one of each size and color available? ○ Draw the tree diagram. The store must stock 17 T-shirts.
Read More >>
  • 1
  • …
  • 5
  • 6
  • 7

Search

  • Home Page
  • Tutorials
  • Mathematics
    • Math 240 – Discrete Math
    • Math 375 – Linear Algebra
    • Math 431 – Intro to Probability
    • Math 514 – Numerical Analysis
    • Math 521 – Analysis I
    • Math 541 – Abstract Algebra
    • Math 632 – Stochastic Processes
    • Abstract Algebra @ 万门大学
    • Linear Algebra @ 万门大学
    • Category Theory
  • Computer Sciences
    • CS/ECE 252 – Intro to Computer Engr.
    • CS/ECE 352 – Digital System Fund.
    • Learn Haskell
  • Course Notes
    • AP Macroeconomics
    • AP Microeconomics
    • AP Chemistry
    • AP Statistics
    • AP Physics C: E＆M
    • AP Physics C: Mechanics
    • CLEP Psychology
  • 2048 Game
  • HiMCM 2016
  • 登峰杯 MCM

WeChat Account

Categories

  • Notes (418)
    • AP (115)
      • AP Macroeconomics (20)
      • AP Microeconomics (23)
      • AP Physics C E＆M (25)
      • AP Physics C Mechanics (28)
      • AP Statistics (19)
    • Computer Sciences (2)
    • Mathematics (300)
      • Abstract Algebra (29)
      • Category Theory (7)
      • Linear Algebra (29)
      • Math 240 (42)
      • Math 375 (71)
      • Math 514 (18)
      • Math 521 (39)
      • Math 541 (39)
      • Math 632 (26)
  • Projects (2)
  • Tutorials (11)

Archives

  • October 2019
  • May 2019
  • April 2019
  • March 2019
  • February 2019
  • December 2018
  • November 2018
  • October 2018
  • September 2018
  • July 2018
  • May 2018
  • April 2018
  • March 2018
  • February 2018
  • January 2018
  • December 2017
  • November 2017
  • October 2017
  • September 2017
  • August 2017
  • July 2017
  • June 2017

WeChat Account

Links

RobeZH's thoughts on Algorithms - Ziyi Zhang
Copyright © 2018.      
TOP