Onetone Blog

2.4 Sequences and Summations

$Introduction • Sequences are ordered lists of elements. ○ 1,2,3,5,8 ○ 1,3,9,27,81,… • Sequences arise throughout mathematics, computer science, and in many other disciplines, ranging from botany to music. • We will introduce the terminology to represent sequences and sums of the terms in the sequences. Sequences • Definition ○ A sequence is a function from a subset of the integers to a set S. ○ The notation a_n is used to denote the image of the integer n. ○ We can think of a_n as the equivalent of f(n) ○ where f is a function from {0,1,2,…..} to S. ○ We call a_n a term of the sequence. • Example ○ Consider the sequence {a_n } where ○ a_n=1/n, {a_n }={a_1,a_2,a_3,…} ○ 1, 1/2,1/3,… Strings • A string is a finite sequence of characters from a finite set (an alphabet). • Sequences of characters or bits are important in computer science. • The empty string is represented by λ. • The string abcde has length 5. Geometric Progression • Definition ○ A geometric progression is a sequence of the form: a,ar,ar^2,…,ar^n,… ○ where the initial term a and the common ratio r are real numbers • Example 1 ○ Let a = 1 and r = −1. Then: ○ {b_n }={b_0,b_1,b_2,b_3,b_4,…}={1,−1,1,−1,1,…} • Example 2 ○ Let a = 2 and r = 5. Then: ○ {c_n }={c_0,c_1,c_2,c_3,c_4,…}={2,10,50,250,1250,…} • Example 3 ○ Let a = 6 and r=1/3. Then: ○ {d_n }={d_0,d_1,d_2,d_3,d_4,…}={6,2, 2/3,2/9,2/27,…} Arithmetic Progression • Definition ○ A arithmetic progression is a sequence of the form ○ a,a+d,a+2d,…,a+nd,… ○ where the initial term a and the common difference d are real numbers • Example 1 ○ Let a = −1 and d = 4: ○ {s_n }={s_0,s_1,s_2,s_3,s_4…}={−1,3,7,11,15…} • Example 2 ○ Let a = 7 and d = −3: ○ {t_n }={t_0,t_1,t_2,t_3,t_4…}={7,4,1,−2,−5…} • Example 3 ○ Let a = 1 and d = 2: ○ {u_n }={u_0,u_1,u_2,u_3,u_4…}={1,3,5,7,9…} Recurrence Relations • A recurrence relation for the sequence {a_n} is an equation that ○ expresses a_n in terms of a_0, a_1, …, a_(n−1) ○ for all integers n with n≥n_0, where n_0 is a nonnegative integer. • A sequence is called a solution of a recurrence relation if its terms satisfy the recurrence relation. • The initial conditions for a sequence specify the terms that precede the first term where the recurrence relation takes effect. • Example ○ Let {a_n} be a sequence that satisfies § the recurrence relation a_n=a_(n−1)+3 for n=1,2,3,4 § and suppose that a_0=2. ○ What are a_1, a_2 and a_3? ○ a_1=a_0+3=2+3=5 ○ a_2=5+3=8 ○ a_3=8+3=11 Fibonacci Sequence • Define the Fibonacci sequence, f0 ,f1 ,f2,…, by: ○ Initial Conditions: f_0=0, f_1=1 ○ Recurrence Relation: f_n=f_(n−1)+f_(n−2) • Find f_2,f_3,f_4,f_5,f_6 ○ f_2=f_1+f_0=1+0=1 ○ f_3=f_2+f_1=1+1=2 ○ f_4=f_3+f_2=2+1=3 ○ f_5=f_4+f_3=3+2=5 ○ f_6=f_5+f_4=5+3=8 Solving Recurrence Relations • Finding a formula for the n-th term of the sequence generated by a recurrence relation is called solving the recurrence relation. • Such a formula is called a closed formula. • Various methods for solving recurrence relations will be covered in Chapter 8 where recurrence relations will be studied in greater depth. • Here we illustrate by example the method of iteration in which we need to guess the formula. The guess can be proved correct by the method of induction (Chapter 5). • Method 1: Working upward, forward substitution ○ Let {a_n} be a sequence that satisfies the recurrence relation ○ a_n=a_(n−1)+3 for n = 2,3,4,… and suppose that a_1=2 ○ a_2=2+3 ○ a_3=(2+3)+3=2+3∙2 ○ a_4=(2+2∙3)+3=2+3∙3 ○ ⋮ ○ a_n=a_(n−1)+3=(2+3∙(n–2))+3=2+3(n–1) • Method 2: Working downward, backward substitution ○ Let {a_n} be a sequence that satisfies the recurrence relation ○ a_n=a_(n−1)+3 for n = 2,3,4,… and suppose that a_1=2 ○ a_n=a_(n−1)+3 ○ =(a_(n−2)+3)+3=a_(n−2)+3∙2 ○ =(a_(n−3)+3)+3∙2=a_(n−3)+3∙3 ○ =… ○ =a_2+3(n–2)=(a_1+3)+3(n–2)=2+3(n–1) Summations • Sum of the terms a_m,a_(m+1),…,a_n from the sequence {a_n } • Notation for a_m+a_(m+1)+…+a_n ○ ∑_(j=m)^n▒a_j • The variable j is called the index of summation. It runs through all the integers starting with its lower limit m and ending with its upper limit n. • More generally for a set S ○ ∑_(j∈S)▒a_j • Examples: ○ r^0+r^1+r^2+r^3+…+r^n=∑_(j=0)^n▒r^j ○ 1+1/2+1/3+1/4+…=∑_(i=1)^∞▒1/i ○ If S={2,5,7,10} then ∑_(j∈S)▒a_j =a_2+a_5+a_7+a_10 Geometric Series • Sums of terms of geometric progressions • Product Notation • Sum of the terms a_m,a_(m+1),…,a_n from the sequence {a_n } • Notation for a_m×a_(m+1)×…×a_n ○ ∏_(j=m)^n▒a_j$

Math 521 – 2/12

$Schwarz Inequality • See Theorem 1.35 in Rudin for a proof of Schwarz Inequality for ℂ ○ For intuition, try proving (x_1 y_2+x_2 y_2 )^2≤(x_1^2+x_2^2 )(y_1^2+y_2^2 ) • Triangle Inequality ○ In a Euclidean Space, |x ⃗⋅y ⃗ |≥|x ⃗ |⋅|y ⃗ | ○ |x ⃗+y ⃗^2 |=|x ⃗ |^2+2x ⃗⋅y ⃗+|y ⃗ |^2≤|x ⃗ |^2+2|x ⃗ ||y ⃗ |+|y ⃗ |^2=(|x ⃗ |+|y ⃗ |)^2 ○ Thus |x ⃗+y ⃗ ||x ⃗ |+|y ⃗ | ○ Let x ⃗≔x ⃗−y ⃗, y ⃗≔y ⃗−z ⃗, we have |x ⃗−z ⃗ ||x ⃗−y ⃗ |+|y ⃗−z ⃗ | Function • Given two sets A and B • A function (or mapping) is a rule that assigns elements in A to elements in B • Notationally, if f is a function from A to B, we write f:A→B • Set A is called the domain of f • Set B is called the codomain of f • For E⊂A, f(E)={b∈B│b=f(e) for some e∈E} is the image of E under f • f(A) is called the range of f • If f(A)=B, then we say that f is onto or surjective • If f(a_1 )=f(a_2 ) implies a_1=a_2, then f is one-to-one or injective • A function that is both one-to-one and onto is said to be bijective • For E⊂B, f^(−1) (E)={a∈A│f(a)∈E} is the inverse image of E under f • Notationally, if y∈B, f^(−1) (y)=f^(−1) ({y}) ○ f^(−1) is at most a single element set for all y∈B if and only if f is injective ○ In this case, f^(−1) can be thought of as a function maps to the single element • Example ○ f:R→R defined by f(x)=x^2 ○ f^(−1) ({1})={1,−1} ○ f^(−1) ({x∈Rx0})=∅ ○ f^(−1) ({0})={0}, we can also write f^(−1) (0)=0 Cardinality • If there exists a one-to-one, onto mapping from set A to set B • We say that A and B can be put in one-to-one correspondence • And that A and B have the same cardinality (or cardinal number) • In this case, we write A~B Equivalence Relation • One-to-one correspondence is an example of an equivalence relation • An equivalence relation satisfies 3 properties ○ Reflexive: A~A ○ Symmetric: If A~B, then B~A ○ Transitivity: If A~B, B~C, then A~C Finite and Countable • Let J_n={1,2,3,…,n} and N={1,2,3,…} • For any set A, we say ○ A is finite if A~J_n for some n (∅~J_0 so ∅ is finite) ○ A is infinite if A≁J_n for all n ○ (To be continued)$

Math 541 – 2/12

$Proposition 15 • Statement ○ |S_n |=n! • Proof ○ First, we prove that if X and Y are sets of order n, then ○ There are n! injective functions from X to Y ○ We argue by induction on n ○ n=1 § Clear ○ n 1 § Suppose f:X→Y is injective § Let x∈X, then there are n possibilities for f(x) § f restricts to an injective function X∖{x}→Y∖{f(x)} § There are (n−1)! such functions, by induction § Thus, there are n(n−1)!=n! injective functions X→Y ○ Now, take X={1,…,n}=Y ○ Then every injection between finite sets of the same order is a bijection ○ Notice that the sets must be finite (Counterexample: f:Z→Z, n↦2n) Cycle • Definition ○ Fix n∈Z( 0). Let a_1,…,a_t∈{1,…,n} ○ The element of S_n given by § a_i↦a_(i+1) for 1≤i≤t−1 § a_t↦a_1 § j↦j if j∉{a_1,…a_t } ○ is denoted by (a_1,a_2,…,a_t ) and is called a cycle of length t • Example ○ Let σ=(1 3 2)∈S_4, then ○ (■8(i&1&2&3&4@↓&↓&↓&↓&↓@σ(i)&3&1&2&4)) ○ Notice: (1 3 2)=(3 2 1)=(2 1 3) Disjoint Cycles • Definition ○ Two cycles (a_1,…a_t ) and (b_1,…,b_k ) are disjoint if ○ {a_1,…a_t }∩{b_1,…,b_k }=∅ • Example ○ (1 2), (3 4)∈S_4 are disjoint • Fact ○ Every element of S_n can be written as a product of disjoint cycles ○ S_1={(1)} ○ S_2={(1),(1 2)} ○ S_3={(1), (1 2), (1 3), (2 3),(1 2 3), (1 3 2)} ○ S_4 = {(1), (1 2), (1 3), (1 4), (2 3), (2 4), (3 4), (1 2 3), (1 2 4), (1 3 2), (1 4 2), (1 3 4), (1 4 3), (2 3 4), (2 4 3), (1 2 3 4), (1 2 4 3), (1 3 2 4), (1 3 4 2), (1 4 2 3), (1 4 3 2), (1 2)(3 4), (1 4)(2 3), (1 3)(2 4s)} ○ Note: We write the identity of S_n as (1) Cycle Decomposition for Permutations • Algorithm Method Example a≔min⁡{x∈Nx not appeared in previous cycles} (1 Begin the new cycle: (a b≔σ(a) σ(1)=12=b If b=a 12≠1 • close the cycle with a right parenthesis So write (1 12 • return to step 1 If b≠a • write b next to a in this cycle: (a b c≔σ(b) σ(12)=8 If c=a 8≠1 • close the cycle with a right parenthesis So continue the cycle as: • return to step 1 (1 12 8 If c≠a • write c next to in this cycle: (a b c b≔c and repeat this step until the cycle closes Naturally this process stops when all the numbers from {1,2, …,n} have appeared in some cycle. σ = (1 1 2 8 10 4)(2 1 3)(3)(5 1 1 7)(6 9) Remove all cycles of length 1 σ = (1 1 2 8 10 4)(2 1 3)(5 1 1 7)(6 9) • Example ○ Take σ∈S_13 to be the following ○ (■8(i&1&2&3&4&5&6&7&8&9&10&11&12&13@↓&↓&↓&↓&↓&↓&↓&↓&↓&↓&↓&↓&↓&↓@σ(i)&12&13&3&1&11&9&5&10&6&4&7&8&3)) ○ Start with 1, σ(1)=12, so write 12 after 1. ○ Keep going until you cycle back to 1 ○ Start with the smallest number which hasn t yet appeared, and repeat. ○ Repeat this step until 1,…,13 have all appeared. Product of Cycles • Reminder: Read from right to left • Example ○ Write σ=(1 2 3)(1 2)(3 4) as a product of disjoint cycles ○ What is σ(1)? § (3 4) maps 1 to 1 § (1 2) maps 1 to 2 § (1 2 3) maps 2 to 3 § Thus σ(1)=3 ○ Similarly σ(3)=4, σ(4)=1 ○ Thus we close the cycle (1 3 4) ○ We won t write down (2), since it is the identity ○ Thus σ=(1 3 4)(2)=(1 3 4) ○ Note: σ∈S_4, but it make sense to think of σ∈S_n for n 4 • Commutativity of S_n ○ (1 2)(1 2 3)=(2 3) ○ (1 2 3)(1 2)=(3 1) ○ In particular S_3 is not abelian ○ Therefore S_n is not abelian for n≥3$

2.3 Functions

$Functions • Definition ○ Let A and B be nonempty sets. ○ A function f from A to B, denoted f:A→B is an assignment of each element of A to exactly one element of B. ○ We write f(a)=b if b is the unique element of B assigned by the function f to the element a of A. ○ Functions are sometimes called mappings or transformations. • Example • Relation ○ A function f:A→B can also be defined as a subset of A×B (a relation). ○ This subset is restricted to be a relation where no two elements of the relation have the same first element. ○ Specifically, a function f from A to B contains one, and only one ordered pair (a,b) for every element a∈A. § ∀x[x∈A→∃y[y∈B∧(x,y)∈f]] § ∀x,y_1,y_2 [[(x,y_1 )∈f∧(x,y_2 )∈f]→y_1=y_2 ] • Terminology ○ Given a function f: A → B: ○ We say f maps A to B or f is a mapping from A to B. § A is called the domain of f. § B is called the codomain of f. ○ If f(a)= b, § then b is called the image of a under f. § a is called the preimage of b. ○ The range of f is the set of all images of points in A under f. § We denote it by f(A). ○ Two functions are equal when § they have the same domain, the same codomain and § map each element of the domain to the same element of the codomain. Representing Functions • Functions may be specified in different ways: • An explicit statement of the assignment. ○ Students and grades example. • A formula. ○ f(x)=x+1 • A computer program. ○ A Java program that when given an integer n, produces n! Example • f(a)=z • The image of d is z • The domain of f is A • The codomain of f is B • The preimage of y is b • f(a)={y,z} • The preimage of z is {a,c,d} • f{a,b,c}={y,z} • f{c,d}={z} Injections • A function f is said to be one-to-one, or injective, • if and only if f(a)=f(b) implies that a=b for all a and b in the domain of f. • A function is said to be an injection if it is one-to-one. Surjections • A function f from A to B is called onto or surjective, • if and only if for every element b∈B there is an element a∈A with f(a)=b. • A function f is called a surjection if it is onto. Bijections • A function f is a one-to-one correspondence, or a bijection, • if it is both one-to-one and onto (surjective and injective). Showing that f is one-to-one or onto • To show that f is injective ○ For x,y,∈A if x≠y then f(x)≠f(y) • To show that f is not injective ○ Find x,y∈A s.t. x≠y and f(x)=f(y) • Example 1 ○ Let f be the function from {a,b,c,d} to {1,2,3} defined by § f(a)=3 § f(b)=2 § f(c)=1 § f(d)=3 ○ Is f an onto function? § Yes, f is onto. § Since all elements of the codomain are images of elements in the domain. ○ If the codomain were changed to {1,2,3,4}, f would not be onto. • Example 2 ○ Is the function f(x) = x^2 from the set of integers to the set of integers onto? ○ No, f is not onto because there is no integer x with x^2 =−1, for example. • Example 3 ○ Let f be the function from the N to the even natural numbers defined by ○ f(n)=2n. Is f an onto function? One to one? ○ f is an onto function, and f is one to one • Example 4 ○ Is the function f(x)=x^3 from R to R onto? One to one? ○ f is an onto function, and f is one to one • Example 5 ○ Is the function f(x)=1/|x| fomr R∖{0} to R onto? One to one? ○ f is not injective, and f is not surjective. Inverse Functions • Let f be a bijection from A to B. • Then the inverse of f, denoted f^(−1) , is the function from B to A defined as • f^(−1) (y)=x iff f(x)=y • No inverse exists unless f is a bijection. Why? • Example Questions • Example 1 ○ Let f be the function from {a,b,c} to {1,2,3} such that § f(a)=2 § f(b)=3 § f(c)=1 ○ Is f invertible and if so what is its inverse? ○ The function f is invertible because it is a one-to-one correspondence. ○ The inverse function f^(−1) reverses the correspondence given by f, so § f^(−1) (1)=c § f^(−1) (2)=b § f^(−1) (3)=a • Example 2 ○ Let f:Z→Z be such that f(x)=x+1. ○ Is f invertible, and if so, what is its inverse? ○ The function f is invertible because it is a one-to-one correspondence. ○ The inverse function f^(−1) reverses the correspondence so f^(−1) (y)=y −1. • Example 3 ○ Let f:R→R be such that f(x)=x^2. ○ Is f invertible, and if so, what is its inverse? ○ The function f is not invertible because it is not one-to-one. Composition • Let f:B→C, g:A→B. • The composition of f with g, denoted f∘g is the function from A to C defined by • f∘g(x)=f(g(x)) • Example Composition Questions • Example 1 ○ If f(x)=x^2 and g(x)=2x+1 ○ Then f(g(x))=(2x+1)^2 ○ And g(f(x))=2x^2+1 • Example 2 ○ Let f and g be functions from the set of integers to the set of integers defined by § f(x)=2x+3 § g(x)=3x+2 ○ What is the composition of f and g, and also the composition of g and f ? § f∘g(x)=f(g(x))=f(3x+2)=2(3x+2)+3=6x+7 § g∘f(x)=g(f(x))=g(2x+3)=3(2x+3)+2=6x+11 Graphs of Functions • Let f be a function from the set A to the set B. • The graph of the function f is the set of ordered pairs {(a,b)┤|a∈A and f(a)=b}. • Example Some Important Functions • The floor function f(x)=⌊x⌋ is the largest integer less than or equal to x. • The ceiling function f(x)=⌈x⌉ is the smallest integer greater than or equal to x • Example ○ ⌈3.5⌉=4, ⌊3.5⌋=3 ○ ⌈−1.5⌉=−1, ⌊−1.5⌋=−2 Factorial Function • f:N→Z+, denoted by f(n) = n! is • the product of the first n positive integers when n is a nonnegative integer. ○ f(n)=1 ∙ 2 ∙∙∙ (n – 1) ∙ n, ○ f(0)=0! = 1 • Examples: ○ f(1)=1!=1 ○ f(2)=2!=1∙2=2 ○ f(6)=6!=1∙2∙3∙4∙5∙6=720 ○ f(20)=2,432,902,008,176,640,000 Partial Function • A partial function f from a set A to a set B is an assignment to each element a in a subset of A, of a unique element b in B. • The sets A and B are called the domain and codomain of f, respectively. • We day that f is undefined for elements in A that are not in the domain of definition of f. • When the domain of definition of f equals A, we say that f is a total function. • Example ○ f:N→Z where f(n)=√n is a partial function from Z to R ○ where the domain of definition is the set of nonnegative integers. ○ Note that f is undefined for negative integers.$

Math 541 – 2/9

$Examples of Orders • Example 1 ○ A≔(■8(0&−1@1&−1))∈GL_2 (R ○ A^3=(■8(0&−1@1&−1))^3=(■8(−1&1@−1&0))(■8(0&−1@1&−1))=(■8(1&0@0&1))=I ○ Thus, |A|=3 • Example 2 ○ In Z,Q,R,ℂ, every nonzero element has infinite order • Example 3 ○ In Q∗ and R∗, the elements of finite order are § |1|=1 § |−1|=2 ○ In ℂ^∗, there are lots more § elements of order n in ℂ are called n^th roots of unity § i is the fourth root of unity § i.e. i^1=i, i^2=−1, i^3=−i, i^4=1 • Example 4 ○ What are the orders of the elements in Z\/6Z? Elements Order Note 0 ̅ 1 0 ̅ is the identity 1 ̅ 6 1 ̅⋅6=6 ̅=0 ̅ 2 ̅ 3 2 ̅⋅3=6 ̅=0 ̅ 3 ̅ 2 3 ̅⋅2=6 ̅=0 ̅ 4 ̅ 3 4 ̅⋅3=(12) ̅=0 ̅ 5 ̅ 6 5 ̅⋅6=(30) ̅=0 ̅ ○ In general, if a ̅∈Z\/nZ, then the "n^th power" of a ̅ is (na) ̅ ○ Note that all the orders are divisors of 6 (Lagrange Theorem) • Example 5 ○ What are the orders of the elements in Z\/5Z×? § Z\/5Z×={1 ̅,2 ̅,3 ̅,4 ̅ } § (0,5)=0≠1, so 0 ̅∉Z\/5Z× Elements Order Note 1 ̅ 1 1 ̅ is the identity 2 ̅ 4 2 ̅^4=(16) ̅=1 ̅ 3 ̅ 4 3 ̅^4=81 ̅=1 ̅ 4 ̅ 2 4 ̅^2=(16) ̅=1 ̅ Symmetric Groups (Section 1.3) • Symmetric Group of Degree n ○ n∈Z(0) ○ S_n≔{bijective functions {1,…,n}→{1,…,n}} ○ S_n is a group with operation given by composition of functions ○ Composition of functions is an operation on S_n § S_n×S_n→S_n § (σ,τ)↦σ∘τ § σ∘τ is again bijictive, so this makes sense ○ Associativity § Suppose f:X→Y, g:Y→Z,h:Z→W § ((hg)∘f)(x)=(hg)(f(x))=h(g(f(x))) § (h(g∘f))(x)=h((g∘f)(x))=h(g(f(x))) § Thus (hg)∘f=h∘(g∘f) ○ Identity § Identity map ○ Inverses § Bijective functions have inverses Proposition 15 • Statement ○ |S_n |=n! • Proof ○ First, we prove that if X and Y are sets of order n, then ○ There are n! injective functions from X to Y ○ We argue by induction on n ○ n=1 § Clear ○ n1 § Suppose f:X→Y is injective § Let x∈X. § There are n possibilities for f(x) § f restricts to an injective function X∖{x}→Y∖{f(x)} § There are (n−1)! such functions, by induction § Thus, there are n(n−1)!=n! injective functions X→Y ○ (To be continued)$

Shawn Zhong

Shawn Zhong

2.4 Sequences and Summations

Math 521 – 2/12

Math 541 – 2/12

2.3 Functions

Math 541 – 2/9

Search

WeChat Account