Report

Mathematical Induction Goals Explain & illustrate construction of proofs of a variety of theorems using mathematical induction. Copyright © Peter Cappello Motivation • Mathematics uses 2 kinds of arguments: • deductive • inductive • Proposition: P( n ): 1 + 2 + … + n = n( n + 1 )/2. • Observe that P(1), P(2), P(3), & P(4). Conjecture: nN P( n ). • Mathematical induction is a finite proof pattern for proving propositions of the form nN P( n ). Copyright © Peter Cappello The Principle of Mathematical Induction • Let P( n ) be a predicate function: nN P( n ) is a proposition. • To prove nN P( n ), it suffices to prove: 1. P( 1 ) is true. 2. nN ( P( n ) P( n + 1 ) ). • This is not magic. • It is a recipe for constructing a finite proof for arbitrary nN. Copyright © Peter Cappello Proving P( 3 ) • Given P( 1 ) n 1 ( P( n ) P( n + 1) ). • Proof: 1. P( 1 ). [premise 1] 2. P( 1 ) P( 2 ). [U.S. of premise 2 for n = 1] 3. P( 2 ). [step 1, 2, & modus ponens] 4. P( 2 ) P( 3 ). [U.S. of premise 2 for n = 2] 5. P( 3 ). [step 2, 3, & modus ponens] • Construct a finite proof for P( 1,999,765 ). Copyright © Peter Cappello Mathematical Induction as the Domino Principle If the 1st domino falls over and the nth domino falls over implies that the ( n + 1 )st domino falls over then domino n falls over for all n N. Copyright © Peter Cappello Mathematical Induction as the Domino Principle 1 2 3 n n +1 Copyright © Peter Cappello The 3-Step Method • The implication in step 2 typically is proved directly. • The proof pattern thus has 3 steps: 1. Prove P( 1 ). [called the basis] 2. Assume P( n ) [called the induction hypothesis] 3. Prove P( n + 1 ) [called the inductive step] • The last 2 steps are for arbitrary n N. • Using P( n ) to prove P( n + 1 ) implies a recursive formulation of P( n ). Copyright © Peter Cappello Induction as a Creative Process • Mathematical induction is similar to, but not identical to, scientific induction. • In both cases, a “theory” is created. • Look at specific cases; perceive a pattern. • Hypothesizing a pattern, a theory, is a creative process (only people who are bad at mathematics say otherwise). • With mathematical induction, a “theory” can be proved. Copyright © Peter Cappello • Scientific theories cannot be proved. • They can be disproved. • A scientific theory can be based on a mathematical model. • Propositions can be proved within the model. • Like axioms, the relationship between: • the mathematical model • physical reality cannot be proven correct. Copyright © Peter Cappello Example • 1=1 • 3=1+2 • 6=1+2+3 • 10 = 1 + 2 + 3 + 4 • What is a general formula, if any, for 1 + 2 + … + n? • Let F( n ): 1 + 2 + . . . + n. • A recursive formulation: F( n ) = F( n - 1 ) + n. Copyright © Peter Cappello A Geometric Interpretation • 1: • 2: • 3: • Put these blocks, which represent numbers, together to form sums: • 1+2= • 1+2+3= Copyright © Peter Cappello n n Area is n2/2 + n/2 = n(n + 1)/2 Copyright © Peter Cappello 1 + 2 + … + n = n(n + 1)/2 A Mathematical Induction Proof • F( 1 ) = 1( 1 + 1 )/2 = 1. • Assume F( n ) = n( n + 1 )/2 • Show F( n + 1 ) = ( n + 1 )( n + 2 )/2. F( n + 1 ) = 1 + 2 + . . . + n + ( n + 1 ) [Definition] = F( n ) + n + 1 [Recursive formulation] = n( n + 1 ) / 2 + n + 1 [Induction hyp.] = n( n + 1 ) / 2 + ( n + 1 ) (2/2) = ( n + 1 ) ( n + 2 ) / 2. Copyright © Peter Cappello • In finding a recursive formulation, we focused on the: • similarities • differences for successive values of n. • Sometimes, it is useful to: • Note the difference between F( n ) & F( n – 1 ). • Find a pattern in this sequence of differences. Copyright © Peter Cappello Example: 3 1 + 3 2 +...+ • Let F( n ) = 13 + 23 + . . . + n3. • What is a formula for F(n)? • 1 = 13 • 9 = 13 + 23 • 36 = 13 + 23 + 33 • 100 = 13 + 23 + 33 + 43 • Do you see a pattern? Copyright © Peter Cappello 3 n =? Prove that n F( n ) = [ n( n + 1 )/2 ]2 1. F( 1 ) = 13 = 1 = [ 1( 2 ) / 2 ]2. 2. Assume F( n ) = [ n( n + 1 ) / 2 ]2 . I.H. 3. Prove F( n + 1 ) = [ ( n + 1 )( n + 2 ) / 2 ]2. F ( n + 1 ) = 13 + 23 + . . . + n3 + ( n +1 )3 Defn. of F( n + 1 ) = F( n ) + ( n + 1 )3 Recursive formulation = [ n( n + 1 )/ 2 ]2 + ( n + 1 )3 Use I. H. = ( n + 1 )2[ ( n / 2 )2 + ( n + 1 ) ] = ( n + 1 )2[ n2 / 4 + ( 4 / 4 )( n + 1 ) ] = ( n +1 )2[ ( n2 + 4n + 4 ) / 4 ] = [ ( n + 1) (n + 2) / 2 ]2. Copyright © Peter Cappello Translating the starting point • If we: • know P( n ) is false for 1 n 9 • think P( n ) is true for n > 9. • Then define Q( n ) = P( n + 9 ). • Use mathematical induction to show that n N Q( n ). • We thus can start the induction at any natural number. Copyright © Peter Cappello Example: Stamps • Suppose the US Post Office prints only 5 & 9 cent stamps. • Prove n > 34, you can make postage for n cents, using only 5 & 9 cent stamps. Let S( n ) denote the statement: You can make postage for n cents using only 5-cent & 9-cent stamps. 1. Basis: For n = 35: Use 7 5-cent stamps. 2. I.H.: Assume S( n ). Copyright © Peter Cappello 3. Prove S( n + 1 ). Case: For S( n ), # of 9-cent stamps used = 0: Only 5-cent stamps are used for S( n ). # of 5-cent stamps ≥ 7. Replace 7 5-cent stamps with 4 9-cent stamps. Case: For S( n ), # of 9-cent stamp used > 0: Replace 1 9-cent stamp with 2 5-cent stamps. Copyright © Peter Cappello Generalizing the Basis • To prove nN P( n ), if suffices to show: • P( 1 ) P( 2 ). • nN( [ P( n ) P( n + 1 ) ] P( n + 2 ) ) • If: • We can push over the first 2 dominos; • Pushing over any 2 adjacent dominos implies pushing over the next domino. then we can push over all the dominos. Copyright © Peter Cappello The Fibonacci Formula • Define the nth Fibonacci number, F( n ), as: • F( 0 ) = 0, F( 1 ) = 1, • F( n ) = F( n – 1 ) + F( n – 2 ). • Prove F( n ) = 5-1/2 ( [ ( 1 + 51/2 ) / 2]n - [ ( 1 - 51/2 ) / 2 ]n ). Basis: F( 0 ) = 5-1/2 ( [ ( 1 + 51/2 ) /2 ]0 - [ (1 - 51/2) / 2 ]0 ) = 0. F( 1 ) = 5-1/2 ( [ ( 1 + 51/2 ) / 2 ]1 - [ ( 1 - 51/2 ) / 2 ]1 ) = ( 5-1/2 / 2 ) ( 1 + 51/2 - 1 + 51/2 ) = 1. Copyright © Peter Cappello The Fibonacci Formula F( n ) = 5-1/2 ( [ ( 1 + 51/2 ) / 2]n - [ ( 1 - 51/2 ) / 2 ]n ) • Let a = ( 1 + 51/2 ) / 2 b = ( 1 - 51/2 ) / 2. • Note: a + 1 = a2 & b + 1 = b2. • Induction hypotheses: F( n ) = 5-1/2 ( an – bn ) F( n +1 ) = 5-1/2 ( an + 1 – bn + 1 ). • Induction step: Show F( n + 2 ) = 5-1/2 ( an + 2 - bn + 2 ). Copyright © Peter Cappello F( n ) = 5-1/2 ( [ ( 1 + 51/2 ) / 2]n - [ ( 1 - 51/2 ) / 2 ]n ) Proof of Induction Step F( n + 2 ) = F ( n + 1 ) + F ( n ) [Definition] = 5-1/2 ( an + 1 – bn + 1 ) + 5-1/2 ( an – bn ) = 5-1/2 ( an + 1 + an – bn + 1 – bn ) = 5-1/2 ( an ( a + 1 ) – bn ( b + 1 ) ). = 5-1/2 ( an + 2 – bn + 2 ) Copyright © Peter Cappello [I.H.] Generalizing this ... • If • P( 1 ) P( 2 ) . . . P( k ) • n { [ P( n + 1 ) P( n + 2 ) . . . P( n + k ) ] P( n + k + 1 ) } • then n N P( n ). Copyright © Peter Cappello End Copyright © Peter Cappello Strong Mathematical Induction • If • P( 1 ) P( 2 ) . . . P( k ) and • for n k, [ P( 1 ) P( 2 ) . . . P( n ) ] P( n + 1 ) • then, n N P(n). Copyright © Peter Cappello Example: Fundamental Theorem of Arithmetic • Prove that all natural numbers 2 can be represented as a product of primes. • Basis: 2: 2 is a prime. • Assume that 1, 2, . . . , n can be represented as a product of primes. Copyright © Peter Cappello • Show that n + 1can be represented as a product of primes. • Case n + 1 is a prime: It can be represented as a product of 1 prime, itself. • Case n + 1 is composite: n = ab, for some a,b < n. • Therefore, a = p1p2 . . . pk & b = q1q2 . . . ql, where the pis & qis are primes. • Represent n = p1p2 . . . pkq1q2 . . . ql. Copyright © Peter Cappello