Report

Strong Induction: Selected Exercises Goal Explain & illustrate proof construction of a variety of theorems using strong induction Strong Induction Domain of discussion is the positive integers, Z+. Strong Induction: If 1. p( 1 ) 2. k ( [ p( 1 ) p( 2 ) … p( k ) ] p( k + 1 ) ) then n p( n ). Copyright © Peter Cappello 2 Example: Fundamental Theorem of Arithmetic Let the universe of discourse be N. Let P( n ) denote “n is a product of primes.” Prove that n 2 P( n ). Basis P( 2 ): Since 2 is prime, 2 is a product of primes. Assume P( 2 ), . . . , P( n ). (Strong induction hypothesis) Copyright © Peter Cappello 3 Show P( n + 1 ): – Case n + 1 is a prime: It is a product of 1 prime: itself. – Case n + 1 is not a prime: 1. n + 1 = ab, such that 1 < a n, 1 < b n 2. P( a ): a = p1p2 . . . pk, where the pis are primes. (S.I.H.) 3. P( b ): b = q1q2 . . . ql, where the qis are primes. (S.I.H.) 4. n + 1 = ( p1p2 . . . pk )( q1q2 . . . ql ). Copyright © Peter Cappello 4 Exercise 10 – A chocolate bar consists of n squares arranged in a rectangle. – The bar can be broken into smaller rectangles of squares with a vertical or horizontal break. – How many breaks suffice to break the bar into n squares? Consider an example bar consisting of 4 x 3 squares. Copyright © Peter Cappello 5 Exercise 10 continued Use strong induction to prove that n - 1 breaks suffice. Basis n = 1: 1 – 1 = 0 breaks suffice. Assume for bars of up to n squares that n – 1 breaks suffice. Show for bars of n + 1 squares that n breaks suffice. 1. Break the bar horizontally, if there is > 1 row, or vertically, if there is only 1 row of squares. Copyright © Peter Cappello 6 Exercise 10 continued 2. Let piece 1 have s1 squares & piece 2 have s2 squares. 3. s1 + s2 = n + 1. 4. s1 - 1 breaks suffice to break piece 1 into squares. (SIH) 5. s2 - 1 breaks suffice to break piece 2 into squares. (SIH) 6. 1 + ( s1 – 1 ) + ( s2 – 1 ) = n breaks suffice. Copyright © Peter Cappello 7 Exercise 30 Find the flaw with the following “proof” that an = 1, n ≥ 0, when a 0 is real. Proof: Basis n = 0: a0 = 1. Inductive step: Assume that aj = 1, 0 j k. Show ak+1 = 1: ak+1 = ( ak .ak ) / ak-1 = 1.1 / 1 = 1. Copyright © Peter Cappello 8 Exercise 30 continued The proof fails for n = 1. Why? Copyright © Peter Cappello 9 Exercise 18 Show: If a convex polygon P with consecutive vertices v1, v2, …, vn is triangulated into n – 2 triangles (Δ), the triangles can be numbered 1, 2, …, n – 2 so that vi is a vertex of Δi, for i = 1, 2, …, n – 2. 6 1 5 2 4Copyright © Peter Cappello 3 2011 10 Exercise 18 Show: If a convex polygon P with consecutive vertices v1, v2, …, vn is triangulated into n – 2 triangles (Δ), the triangles can be numbered 1, 2, …, n – 2 so that vi is a vertex of Δi, for i = 1, 2, …, n – 2. 1 6 1 5 2 4 2 3 4Copyright © Peter Cappello 3 2011 11 Exercise • What is the P( n ) that is claimed? • For what n is it claimed to be true? • What is a recursive formulation of P( n )? Copyright © Peter Cappello 12 1 Exercice18 Proof 1 3 Basis n = 3: True, as shown. 2 Assume proposition for polygons of k vertices, where 3 k n - 1. Show proposition for polygons with n vertices. 1. For n > 3, every triangulation of P includes a diagonal from vn or vn-1. (If not, P is not triangulated.) 2. Case: A diagonal connects vn to vk: 6 1 5 2 Copyright © Peter Cappello 2011 4 3 13 18 Proof continued Subdivide P into 2 smaller polygons, P1 & P2, defined by this diagonal: P1 has vertices v1, v2, …, vk, vn. Renumber vn of P1 as vk+1; (k – 1 triangles when triangulated) 4 1 2 Copyright © Peter Cappello 2011 3 14 18 Proof continued Subdivide P into 2 smaller polygons, P1 & P2, defined by this diagonal: P1 has vertices v1, v2, …, vk, vn. Renumber vn of P1 as vk+1; (k – 1 triangles when triangulated) Triangulate P1 with triangles properly numbered 1, …, k – 1. (SIH) 4 1 1 2 Copyright © Peter Cappello 2011 3 2 15 18 Proof continued P2 has vertices vk, vk+1, …, vn. P2 has n – k + 1 vertices; (n – k – 1 triangles) For each vi of P2, renumber vertices v’i = vi – k +1. 4= 6 - 2 3= 5 - 2 Copyright © Peter Cappello 2011 2= 4 - 2 1= 3 – 2 16 18 Proof continued P2 has vertices vk, vk+1, …, vn. For each vi of P2, renumber vertices v’i = vi – k +1. P2 has n – k + 1 vertices; (n – k – 1 triangles) Triangulate it with triangles properly numbered 1, …, n – k – 1. (SIH) 4 3 2 1 Copyright © Peter Cappello 2011 2 1 17 18 Proof continued P2 has vertices vk, vk+1, …, vn. For each vi of P2, renumber vertices v’i = vi – k +1. P2 has n – k + 1 vertices; (n – k – 1 triangles) Triangulate it with triangles properly numbered 1, …, n – k – 1. (SIH) Add k – 1 to each triangle number: k, k + 1, …, n – 2. 4 3 4 3 Copyright © Peter Cappello 2011 2 1 18 18 Proof continued P2 has vertices vk, vk+1, …, vn. For each vi of P2, renumber vertices v’i = vi – k +1. P2 has n – k + 1 vertices; (n – k – 1 triangles) Triangulate it with triangles properly numbered 1, …, n – k – 1. (SIH) Add k – 1 to each triangle number: k, k + 1, …, n – 2. Original vertex vi now participates in Δi, i = k, …, n – 2. 6 1 1 5 4 2 3 Copyright © Peter Cappello 2011 4 3 2 19 18 Proof continued 3. Case: A diagonal connects vn-1 to vk: This case is handled similarly. Do this as an exercise. This constructive proof is essentially a recursive algorithm for computing these triangles & their numbers. Copyright © Peter Cappello 20 End Copyright © Peter Cappello 21 40 Well-ordering principle: Every nonempty set of nonnegative integers has a least element. Use the well-ordering principle to show that [x, y R x < y] r Q, x < r < y. Copyright © Peter Cappello 2011 22 40 Proof 1. y – x > 0. 2. 1/(y – x) > 0. 3. Let a Z, a > 1/(y – x). 4. y – x > 1/a. 5. Choose the least positive j such that └x┘+ j/a > x. (WOP) 6. Let r = └x┘+ j/a. 7. r Q. (└x┘, j, a Z) 8. x < r. (defn of r) 9. └x┘+ (j – 1)/a < x. (choice of j) 10. r – 1/a < x. (defn of r.) 11. r – (y – x) < x. (step 10 & 4) 12. r < y. 23 Characters • ≥≡~┌┐└┘ • ≈ • • Ω Θ • Σ • Copyright © Peter Cappello 24