March 19, 2018 - Shawn Zhong

Math 541 – 3/19

$Recall • ϵ:S_n→Z\/2Z σ↦{■8(0 ̅&σ is a product of even number of transposition@1 ̅&σ is a product of odd number of transposition)┤ • ϵ^′:S_n→Z\/2Z σ↦{■8(0 ̅&σ(Δ)=Δ@1 ̅&σ(Δ)=−Δ)┤ • Δ≔∏_(1≤i j≤n)▒(x_i−x_j ) , σ(Δ)≔∏_(1≤i j≤n)▒(x_σ(i) −x_σ(j) ) Proposition 40 • Statement ○ Let n∈Z( 0) ○ If τ∈S_n is transposition, then ϵ^′ (τ)=1 ̅ • Example ○ When n=4, τ=(1 2) ○ Δ=(x_1−x_2 )(x_1−x_3 )(x_1−x_4 )(x_2−x_3 )(x_2−x_4 )(x_3−x_4 ) ○ τ(Δ)=(x_2−x_1 )(x_2−x_3 )(x_2−x_4 )(x_1−x_3 )(x_1−x_4 )(x_3−x_4 ) ○ τ(Δ)=−Δ⇒ϵ^′ (τ)=1 ̅ • Proof: Suppose τ=(1 2) ○ Say (x_i−x_j ) is a factor of Δ ○ Then τ(i) τ(j)⟺i=1,j=2 ○ Thus τ(Δ)=−Δ ○ So ϵ^′ (τ)=1 ̅ • Proof: Suppose τ=(i j), 1≤i j≤n ○ Let λ∈S_n denote the following permutation § λ(1)=i § λ(2)=j § λ(i)=1 § λ(j)=2 § λ(k)=k,k∉{1,2,i,j} ○ (i j)=λ(1 2)λ § [λ(1 2)λ](i)=[λ(1 2)](1)=λ(2)=j § [λ(1 2)λ](j)=[λ(1 2)](2)=λ(1)=i § Without loss of generality, assume i,j∉{1,2} § [λ(1 2)λ](1)=[λ(1 2)](i)=λ(i)=1 § [λ(1 2)λ](2)=[λ(1 2)](j)=λ(j)=2 § For k∉{1,2,i,j} § [λ(1 2)λ](k)=[λ(1 2)](k)=λ(k)=k ○ We know ϵ′ is a homomorphism, so § ϵ^′ (i j)=ϵ^′ (λ(1 2)λ) § =ϵ^′ (λ)+ϵ^′ (1 2)+ϵ^′ (λ) § =2ϵ^′ (λ)+1 ̅ § =0 ̅+1 ̅=1 ̅ Corollary 41 • Statement ○ ϵ is well-defined, and ϵ=ϵ^′ • Proof ○ Let σ∈S_n ○ Say σ=τ_1⋯τ_n where τ_i is a transposition, then ○ ϵ^′ (σ)=ϵ^′ (τ_1 )+…+ϵ^′ (τ_n )=⏟(1 ̅+⋯+1 ̅ )┬(n copies)=n ̅ ○ Thus if n is odd, σ cannot be written as a product of an even number of transpositions, and vice versa ○ This shows ϵ is well-defined, and ϵ=ϵ^′ Corollary 42 • Statement ○ If n≥2, ϵ is surjective • Proof ○ ϵ(1)=0 ̅, and ϵ(1 2)=1 ̅ ○ Since Z\/2Z has only 2 elements, ϵ is surjective Alternating Group • Definition ○ The alternative group, denoted as A_n is the kernel of ϵ ○ That is, A_n contains of all even permutations in S_n • Order of A_n ○ By the First Isomorphism Theorem ○ We have an isomorphism S_n \/A_n≅Z\/2Z ○ By Lagrange s Theorem, |A_n |[S_n:A_n ]=|S_n | ○ ⇒|A_n |=|S_n |/[S_n:A_n ] =n!/2 • Note ○ We showed earlier that, if (a_1…a_t )∈S_n, ○ (a_1…a_t )=⏟((a_1 a_t )(a_1 a_(t−1) )⋯(a_1 a_2 ) )┬(t−1 terms) ○ t\-cycle is even when t is odd, and vise versa ○ Thus, (a_1…a_t )∈A_n⟺t is odd • Examples ○ A_2= trivial group ○ A_3={(1), (1 2 3),(1 3 2)}=⟨(1 2 3)⟩ ○ A_4= {(1), (1 2 3), (1 3 2), (1 2 4), (1 4 2), (1 3 4), (1 4 3), (2 3 4), (2 4 3), (1 2)(3 4), (1 3)(2 4), (1 4)(2 3)} • Subgroups of A_4 Order Subgroup 1 {(1)} 2 3 cyclic subgroups 3 4 cyclic subgroups 4 Homework 6 None 12 A_4 Converse of Lagrange s Theorem • A_4 has no subgroup of order 6 • This shows that the converse of Lagrange s Theorem is false ○ If ├ d┤|├ |G|┤, there is not necessarily a subgroup of G with order d • But the converse does hold for finite cyclic groups • Cauchy s Theorem ○ If p is a prime, and ├ p┤|├ |G|┤, then G contains a subgroup of order p • Sylow s Theorem ○ If |G|=p^α m, where p is prime and p∤m ○ Then G contains a subgroup of order p^α$

Math 541 – 3/16

$Homework 6 Question 1 • Statement ○ Suppose A,B⊴H, AB=H ○ Then there is an isomorphism H⁄(A∩B) →┴≅ (H⁄A)×(H⁄B) • Proof ○ Define a map § f:H→(H⁄A)×(H⁄B) h↦(h�,h�) ○ Check f is a homomorphism § f(h1 h2 ) § =(h1 h2 A,h1 h2 B) § =(h1 Ah2 A,h1 Bh2 B) § =(h1 A,h1 B)(h2 A,h2 B) § =f(h1 )f(h2 ) ○ Compute ker⁡f § Let h∈ker⁡f § ⟺f(h=(1_(H\/A),1_(H\/B) )=(A,B) § ⟺h∈A and h∈B § ⟺h∈A∩B § Therefore ker⁡f=A∩B ○ Prove surjectivity § Let (h1 A,h2 B)∈(H⁄A)×(H⁄B) § Choose a_1,a_2∈A, b_1,b_2∈B s.t. □ h1=a_1 b_1 □ h2=a_2 b_2 § Then □ h1 A=Ah1=Aa_1 b_1=Ab_1 □ h2 B=a_2 b_2 B=a_2 B § f(a_2 b_1 )=(h1 A,h2 B) □ f(a_2 b_1 ) □ =(a_2 b_1 A,a_2 b_1 B) □ =(Aa_2 b_1,a_2 B) □ =(Ab_1,a_2 B) □ =(h1 A,h2 B) § Therefore f is surjective ○ By the First Isomorphism theorem § There is an isomorphism § f ̅:H⁄ker⁡f →im f § f ̅:H⁄(A∩B)→(H⁄A)×(H⁄B) • Note ○ Given two homomorphism f_1:G→H_1, f_2:G→H_2 ○ Then their direct product given by § f:G→H_1×H_2 g→(f_1 (g),f_2 (g)) ○ is also a homomorphism Homework 6 Question 2 • Statement ○ G is abelian ⟺ G\/Z(G) is cyclic • Proof (⟹) ○ Suppose G is abelian, then ○ G=Z(G) ○ So G\/Z(G) is the trivial group ○ Therefore G\/Z(G) is cyclic • Proof (⟸) ○ Suppose G\/Z(G) is cyclic ○ Choose gZ(G)∈G\/Z(G) s.t. ⟨gZ(G)⟩=G\/Z(G) ○ Let x∈G ○ Then xZ(G)=g^k Z(G) for some k∈Z, and g^(−k) x∈Z(G) ○ Let a,b∈G ○ Choose k_1,k_2∈Z and z_1,z_2∈Z(G) s.t ○ g^(−k_1 ) a=z_1 and g^(−k_2 ) b=z_2 ○ So, a=g^(k_1 ) z_1, b=g^(k_2 ) z_2 ○ Then ab=g^(k_1 ) z_1 g^(k_2 ) z_2=g^(k_2 ) z_2 g^(k_1 ) z_1=ba Homework 6 Question 4 • Statement ○ G=⟨g⟩ is cyclic of order n, d|n, d 0 ○ Then G⁄⟨g^d ⟩ is cyclic of order d • Proof: If H is a cyclic group and A≤H, then H\/A is also cyclic ○ Choose a generator h∈H ○ Then hA is a generator of H\/A ○ If h′ A∈H\/A ○ Choose k∈Z s.t. h′=hk ○ Therefore h′ A=hk A=(h�)^k • Proof ○ |⟨g^d ⟩|=n/((n,d) )=n/d ○ By Lagrange s Theorem ○ n=|G|=|⟨g^d ⟩|⋅[G:⟨g^d ⟩]=n/d |G⁄⟨g^d ⟩ | ○ ⇒|G⁄⟨g^d ⟩ |=d Theorem 37 (The Correspondence Theorem) • Statement ○ Let G be a group, and let N⊴G, then ○ there is a bijection {subgroups of G\/N} (⇄┴F)┬F′ {subgroups of G containing N} • Proof ○ Define § F^′ (K)=K\/N≔{gN∈G\/N│g∈K} § F(H)={g∈G│gN∈H} ○ F(H) is a subgroup of G containing N § If n∈N, then nN=id_(G\/N)∈H § Thus, N⊆F(H) § This also shows that F(H)≠∅ § If g_1,g_2∈F(H), then § g_1 N,g_2 N∈H⇒g_1 N(g_2 N)^(−1)=g_1 g_2^(−1) N∈H⇒g_1 g_2^(−1)∈F(H) ○ F∘F′ and F^′∘F are the identity maps § (F∘F^′ )(K)=F(K\/N)={g∈G│gN∈K\/N}=K § (F^′∘F)(H)=F^′ ({g│gN∈H})={g│gN∈H}⁄N=H$

Math 541 – 3/14

$Proposition 38 • Definition ○ Fix n to be a positive integer ○ A 2\-cycle (i j) in S_n is a transposition • Statement ○ Every σ∈S_n can be written as a product of transposition • Example ○ (1 5 3 2 4)=(1 4)(1 2)(1 3)(1 5) ○ (3 5)=(1 5)(1 3)(1 5) • Proof ○ Fix σ∈S_n ○ We may assume σ is a cycle σ=(a_1 a_2… a_t ) ○ By induction on t, we claim § (a_1 a_2… a_t )=(a_1 a_t )(a_1 a_(t−1) )…(a_1 a_2 ) ○ Base case: t=2 § (a_1 a_2 )=(a_1 a_2 ) ○ Inductive step: t 2 § (a_1 a_t )(a_1 a_(t−1) )…(a_1 a_2 ) § =(a_1 a_t )(a_1 a_2… a_(t−1) ) § =(a_1 a_2… a_(t−1) a_t ) • Note ○ S_n is generated by {(1 2),(1 3),…,(1 n)} Sign of Permutation • Intuition ○ The numbers of transposition used to write some σ∈S_n ○ is not well-defined, but it is always either even or odd • Definition ○ Let ϵ:S_n→Z\/2Z σ↦{■8(0 ̅&σ is a product of even number of transposition@1 ̅&σ is a product of odd number of transposition)┤ ○ Then ϵ is a group homomorphism ○ A_n≔ker⁡ϵ is the alternating group of degree n • Auxiliary Polynomial Δ ○ Δ≔∏_(1≤i j≤n)▒(x_i−x_j ) ○ For σ∈S_n, define σ(Δ)≔∏_(1≤i j≤n)▒(x_σ(i) −x_σ(j) ) ○ Then σ(Δ) is always either Δ or −Δ • Example ○ Let n=4 and σ=(1 2 3 4) ○ Δ=(x_1−x_2 )(x_1−x_3 )(x_1−x_4 )(x_2−x_3 )(x_2−x_4 )(x_3−x_4 ) ○ σ(Δ)=(x_2−x_3 )(x_2−x_4 )(x_2−x_1 )(x_3−x_4 )(x_3−x_1 )(x_4−x_1 )=−Δ • Definition ○ Let ϵ^′:S_n→Z\/2Z σ↦{■8(0 ̅&σ(Δ)=Δ@1 ̅&σ(Δ)=−Δ)┤ ○ ϵ^′ (σ) is the sign of σ, often denoted as sgn⁡σ ○ σ is even if ϵ^′ (σ)=0 ̅ ○ σ is odd if ϵ^′ (σ)=1 ̅ Proposition 39 • Statement ○ ϵ′ is a group homomorphism • Example ○ Let σ=(1 2), τ=(1 2 3) ○ Let Δ=(x_1−x_2 )(x_1−x_3 )(x_2−x_3 ) § σ(Δ)=(x_2−x_1 )(x_1−x_3 )(x_2−x_3 )=−Δ § τ(Δ)=(x_2−x_3 )(x_2−x_1 )(x_3−x_1 )=(−1)^2 Δ=Δ ○ σ=(1 2), τ=(1 2 3)⇒τσ=(1 3) § (τσ)(Δ)=(x_3−x_2 )(x_3−x_1 )(x_2−x_1 )=(−1)^3 Δ=−Δ ○ ϵ^′ (τσ)=ϵ^′ (τ) ϵ^′ (σ), since § ϵ^′ (τσ)=1 ̅ § ϵ^′ (τ) ϵ^′ (σ)=0 ̅+1 ̅=1 ̅ • Proof ○ Fix σ,τ∈S_n ○ Let Δ≔∏_(1≤i j≤n)▒(x_i−x_j ) , then § τ(Δ)=∏_(1≤i j≤n)▒(x_τ(i) −x_τ(j) ) § σ(Δ)=∏_(1≤i j≤n)▒(x_σ(i) −x_σ(j) ) § (τσ)(Δ)=∏_(1≤i j≤n)▒(x_(τσ)(i) −x_(τσ)(j) ) ○ Suppose σ(Δ) has k "reversed factor" i.e. factors (x_j−x_i ) where i j § (τσ)(Δ)=∏_(1≤i j≤n)▒(x_τ(σ(i)) −x_τ(σ(j)) ) § =(−1)^k ∏_(1≤i j≤n)▒(x_τ(i) −x_τ(j) ) § =(−1)^k τ(Δ) § =σ(Δ)τ(Δ) ○ Therefore ϵ^′ (τσ)=ϵ^′ (τ) ϵ^′ (σ)$

Math 521 – 3/19

$Cauchy Sequence • A sequence {p_n } in a metric space X is said to be Cauchy sequence • If ∀ε 0, ∃N∈N s.t. d(p_n,p_m ) ε,∀n,m≥N Diameter • Let E be a nonempty subset of metric space X • Let S be set of all real numbers of the form d(p,q) with p,q∈E • Then diam S≔sup⁡S is called the diameter of E (possibly ∞) • If {p_n } is a sequence in X and E={p_N,p_(N+1),…} • Then {p_n } is a Cauchy sequence if and only if (lim)_(N→∞)⁡〖diam E_N 〗=0 Theorem 3.10 • Statement (a) ○ If E ̅ is the closure of a set E in a metric space X, then diam E ̅=diam E • Proof (a) ○ diam E≤diam E ̅ § This is obvious since E⊂E ̅ ○ diam E ̅≤diam E § Let p,q∈E ̅ § Let ε 0, then ∃p^′,q^′∈E s.t. d(p,p′) ε/2, d(q,q′) ε/2 § d(p,q)≤diam E □ d(p,q)≤d(p,p^′ )+d(p^′,q^′ )+d(q^′,q) □ ε/2+d(p^′,q^′ )+ε/2 □ =ε+d(p^′,q^′ ) □ ≤ε+diam E □ Since ε 0 was arbitrary, d(p,q)≤diam E § So diam E ̅≤diam E ○ Therefore diam E ̅=diam E • Statement (b) ○ If K_n is a sequence of compact sets in X s.t. ○ K_n⊃K_(n+1),∀n and (lim)_(n→∞)⁡〖diam K_n 〗=0 ○ Then ⋂24_(n=1)^∞▒K_n consists of exactly one point • Proof (b) ○ Let K=⋂24_(n=1)^∞▒K_n ○ By Theorem 2.36, K is not empty ○ If K contains more than one point, diam K 0 ○ But K_n⊃K, ∀n∈N, then ○ diam K_n≥diam K 0⇒lim_(n→∞)⁡〖K_n 〗≥diam K 0 ○ This contradicts lim_(n→∞)⁡〖diam K_n 〗=0 ○ There can only be one point in K$

5.3 Recursive Definitions and Structural Induction

$Recursively Defined Functions • Definition ○ A recursive or inductive definition of a function consists of two steps. ○ Basis Step § Specify the value of the function at zero. ○ Recursive Step § Give a rule for finding the at an integer from its values at smaller integers ○ A function f(n) is the same as a sequence a_0,a_1,… where f(i)=a_i ○ This was done using recurrence relations in Section 2.4 • Example 1 ○ Suppose f is defined by § f(0)=3 § f(n+1)=2f(n)+3 ○ Find f(1), f(2), f(3), f(4) § f(1)=2f(0)+3=2∙3+3=9 § f(2)=2f(1)+3=2∙9+3=21 § f(3)=2f(2)+3=2∙21+3=45 § f(4)=2f(3)+3=2∙45+3=93 • Example 2 ○ Give a recursive definition of the factorial function n! ○ f(0) = 1 ○ f(n + 1) = (n + 1)∙ f(n) • Example ○ Give a recursive definition of ∑_(k=0)^n▒a_k ○ The first part of the definition is § ∑_(k=0)^0▒a_k =a_0 ○ The second part is § ∑_(k=0)^(n+1)▒a_k =(∑_(k=0)^n▒a_k )+a_(n+1) Fibonacci Numbers • The Fibonacci numbers are defined as follows: ○ f_0=0 ○ f_1=1 ○ f_n=f_(n−1)+f_(n−2) • Find f_2,f_3,f_4,f_5 ○ 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 • Show that whenever n ≥ 3, f_n α^(n−2), where α=(1+√5)/2 ○ Let P(n) be the statement f_n α^(n−2) . ○ Use strong induction to show that P(n) is true whenever n≥3. ○ Basis step § P(3) holds since α 2 = f_3 § P(4) holds since α^2 = (3+√5)/2 3 = f_4 ○ Inductive step § Assume that P(j) holds § i.e., f_j α^(j−2) for all integers j with 3 ≤ j ≤ k, where k ≥ 4. § Show that P(k+1) holds, i.e., f_(k+1) α^(k−1). § Since α^2= α + 1 (because α is a solution of x^2−x−1=0), § α^(k−1)=α^2⋅α^(k−3)=(α+1)⋅α^(k−3)=α⋅α^(k−3)+1⋅α^(k−3)=α^(k−2)+α^(k−3) § By the inductive hypothesis, because k ≥ 4 we have □ f_(k−1) α^(k−3) □ f_k α^(k−3) § Therefore, it follows that □ f_(k+1)=f_k+f_(k−1) α^(k−2)+α^(k−3)=α^(k−1) § Hence, P(k+1) is true. Lamé’s Theorem • Lamé’s Theorem ○ Let a and b be positive integers with a≥b. ○ Then the number of divisions used by the Euclidian algorithm to find gcd(a,b) ○ is less than or equal to five times the number of decimal digits in b. • Proof ○ When we use the Euclidian algorithm to find gcd(a,b) with a≥b, ○ n divisions are used to obtain (with a=r_0,b=r_1) § r_0=r_1 q_1+r_2, 0 r_2 r_1 § r_1=r_2 q_2+r_3, 0 r_3 r_2 § ⋮ § r_(n−2)=r_(n−1) q_(n−1)+r_n, 0 r_n r_(n−1) § r_(n−1)=r_n q_n ○ Since each quotient q_1,q_2,…,q_(n−1) is at least 1 and q_n≥2 § r_n≥1=f_2 § r_(n−1)≥2r_n≥2f_2=f_3 § r_(n−2)≥r_(r−1)+r_n≥f_3+f_2=f_4 § ⋮ § r_2 r_3+r_4≥f_(n−1)+f_(n−2)=f_n § b=r_1≥r_2+r_3≥f_n+f_(n−1)=f_(n+1) ○ If n divisions are used to find gcd(a,b) with a≥b, then b ≥ f_(n+1) ○ By Example 4, f_(n+1) α^(n−1), for n 2, where α=(1+√5)/2. ○ Therefore, b α^(n−1). ○ Because log_10⁡α ≈ 0.208 1/5, log_10⁡b (n−1) log_10⁡α (n−1)/5 ○ Hence, n−1 5⋅log_10⁡b ○ Suppose that b has k decimal digits. Then b 10k and log_10⁡b k. ○ It follows that n−1 5k and since k is an integer, n≤5k. ○ Therefore, O(log b) divisions are used to find gcd(a,b) whenever a b. ○ The number of divisions needed is less than or equal to 5⋅(log_10⁡b+1) ○ Since the number of decimal digits in b is less than or equal to log_10⁡b+1 Recursively Defined Sets and Structures • Recursive definitions of sets have two parts: ○ The basis step specifies an initial collection of elements. ○ The recursive step gives the rules for forming new elements in the set from those already known to be in the set. • Sometimes the recursive definition has an exclusion rule, which specifies that ○ the set contains nothing other than those elements specified in the basis step ○ and generated by applications of the rules in the recursive step. • We always assume that the exclusion rule holds, even if it is not explicitly mentioned. • Example: Subset of Integers S ○ Basis step: 3 ∊ S. ○ Recursive step: If x ∊ S and y ∊ S, then x+y is in S. ○ Initially 3 is in S, then 3 + 3 = 6, then 3 + 6 = 9, etc. • Example: The natural numbers N. ○ Basis step: 0 ∊ N. ○ Recursive step: If n is in N, then n + 1 is in N. ○ Initially 0 is in N, then 0 + 1 = 1, then 1 + 1 = 2, etc. Strings • Definition: The set Σ* of strings over the alphabet Σ: ○ Basis step: λ ∊ Σ* (λ is the empty string) ○ Recursive step: If w is in Σ* and x is in Σ, wx∈Σ^∗. • Example ○ If Σ = {0,1} ○ The strings in in Σ* are the set of all bit strings, λ, 0, 1, 00,01,10, 11, etc. • Example ○ If Σ = {a,b}, show that aab is in Σ*. ○ Since λ ∊ Σ* and a ∊ Σ, a ∊ Σ*. ○ Since a ∊ Σ* and a ∊ Σ, aa ∊ Σ*. ○ Since aa ∊ Σ* and b ∊ Σ, aab ∊ Σ*. String Concatenation • Two strings can be combined via the operation of concatenation. • Let Σ be a set of symbols and Σ* be the set of strings formed from the symbols in Σ. • We can define the concatenation of two strings, denoted by ∙, recursively as follows: ○ Basis step § If w∈Σ^∗, then w⋅λ=w ○ Recursive step § If w_1∈Σ^∗ and w_2∈Σ^∗ and x∈Σ^∗ then w_1⋅(w_2 x)=(w_1⋅w_2 )x • Often w_1⋅w_2 is written as w_1 w_2. • If w_1 = abra and w_2 = cadabra, the concatenation w_1 w_2 = abracadabra. Length of a String • Give a recursive definition of l(w), the length of the string w. • The length of a string can be recursively defined by: ○ l(λ)=0 ○ l(wx) = l(w) + 1 if w∊Σ* and x∈Σ Rooted Trees • The set of rooted trees, where a rooted tree consists of ○ a set of vertices containing a distinguished vertex called the root ○ edges connecting these vertices • can be defined recursively by these steps • Basis step ○ A single vertex r is a rooted tree. • Recursive step ○ Suppose that T_1,…,T_n are disjoint rooted trees with roots r_1,…,r_n respectively. ○ Then the graph formed by § start with a root r, which is not in any of the rooted trees T_1,…,T_n § add an edge from r to each of the vertices r_1,…,r_n ○ is also a rooted tree. Full Binary Trees • The set of full binary trees can be defined recursively by these steps. ○ Basis step § There is a full binary tree consisting of only a single vertex r. ○ Recursive step § If T_1 and T_2 are disjoint full binary trees § There is a full binary tree, denoted by T_1∙T_2, consisting of □ a root r □ edges connecting the root to each of the roots of T_1 and T_2 • The height h(T) of a full binary tree T is defined recursively as follows: ○ Basis step § The height of a full binary tree T consisting of only a root r is h(T)=0 ○ Recursive step § If T_1 and T_2 are full binary trees § Then the full binary tree T=T_1⋅T_2 has height § h(T)=1+max⁡(hT_1 ),hT_2 )) • The number of vertices n(T) of a full binary tree T is defined recursively as follows ○ Basis step § n(T)=1 for full binary tree T consisting of only a root r ○ Recursive step § If T_1 and T_2 are full binary trees § Then the full binary tree T=T_1⋅T_2 has the number of vertices § n(T)=1+n(T_1 )+n(T_2 ) Structural Induction • To prove a property of the elements of a recursively defined set, we use structural induction • Basis step ○ Show that The result holds for all elements specified in the basis step • Recursive step ○ Suppose the statement is true for each of the elements used to construct new elements in the recursive step of the definition ○ Show that the result holds for these new elements. • The validity of structural induction can be shown to follow from the principle of mathematical induction. Structural Induction and Binary Trees • If T is a full binary tree, then n(T)≤2^(hT)+1)−1 • Proof: Use structural induction • Basis step ○ The result holds for a full binary tree consisting only of a root ○ n(T) = 1 and h(T) = 0 ○ Hence, n(T) = 1 ≤ 2^(0+1)−1 = 1 • Recursive step ○ Assume n(T_1 )≤2^(hT_1 )+1)−1 and n(T_2 )≤2^(hT_2 )+1)−1 for full binary trees T_1,T_2 ○ n(T)=1+n(T_1 )+n(T_2 ) ○ ≤1+(2^(hT_1 )+1)−1)+(2^(hT_2 )+1)−1) ○ ≤2⋅max⁡(2^(hT_1 )+1),2^(hT_2 )+1) )−1 ○ =2⋅2^max⁡〖(h(T_1 ),hT_2 ))+1〗 −1 ○ =2⋅2^ht) −1 ○ =2^(ht)+1)−1$

Shawn Zhong

Shawn Zhong

Math 541 – 3/19

Math 541 – 3/16

Math 541 – 3/14

Math 521 – 3/19

5.3 Recursive Definitions and Structural Induction

Search

WeChat Account