Report

Chapter 4 Sequences and Mathematical Induction 4.2 Mathematical Induction Mathematical Induction • A recent method for proving mathematical arguments. • De Morgan is credited with its discovery and and name. • The validity of proof by mathematical induction is taken as a axiom. – an axiom or postulate is a proposition that is not proved or demonstrated but considered to be either self-evident, or subject to necessary decision. (Wikipedia) Principle of Mathematical Induction • Let P(n) be a property that is defined for integers n, and let a be a fixed integer. Suppose the following two statements are true: 1. P(a) is true. 2. For all integers k ≥ a, if P(k) is true then P(k+1) is true. • Then the statement, for all integers n ≥ a, P(a) is true Example • For all integers n ≥ 8, n cents can be obtained using 3 cents and 5 cents. • or, for all integers n ≥ 8, P(n) is true, where P(n) is the sentence “n cents can be obtained using 3 cents and 5 cents.” Example • This can be proven by exhaustion if we can continue to fill in the table up to $1.00. • The table shows how to obtain k cents using 3 and 5 coins. We must show how to obtain (k+1) cents. • Two cases: – k: 3 + 5, k+1: ? • replace 5 with 3 + 3 – k: 3 + 3 + 3, k+1: ? • replace 3+3+3 with 5+5 Method of Proof Mathematical Induction • Statement: “For all integers n≥a, a property P(n) is true.” • (basis step) Show that the property is true for n = a. • (inductive step) Show that for all integers k≥a, if the property is true for n=k then it is true for n=k+1. – (inductive hypothesis) suppose that the property is true for n=k, where k is any particular but arbitrarily chosen integer with k≥a. – then, show that the property is true for n = k+1 Example Coins Revisited • Proposition 4.2.1: Let P(n) be the property “n cents can be obtained using 3 and 5 cent coins.” Then P(n) is true for all integers n≥8. – Proof: – Show that the property is true for n=8: • The property is true b/c 8=3+5. Example cont. – Show that for all integers k≥8, if the property true for n=k, then property true for n=k+1 • (inductive hypothesis) Suppose k cents can be obtained using 3 and 5 cent coins for k≥8. • Must show (k+1) cents can be obtained from 3 & 5 coin. – Case (3,5 coin): k+1 can be obtained by replacing the 5 coin with two 3 cent coins. This increments the value by 1 (3+3=6) replaces the 5 cent coin. – Case (3,3,3 coin): k+1 can be obtained by replacing the three 3 coins with two 5 coins. k=b+3+3+3=b+9 and k+1=b+9+1=b+5+5=b+10 Example Formula • Prove with mathematical induction n(n 1) 1 2 ... n ,n 1 2 • Identify P(n) n(n 1) P(n) 1 2 ... n ,n 1 2 • Basis step 1(11) 2 P(1) 1 1 2 2 Example Formula cont. • Inductive step – assume P(k) is true, k>=1 k(k 1) P(k) 1 2 ... k 2 k+1 for n – show that P(k+1) is true by subing (k 1)(k 11) (k 1)(k 2) P(k 1) 1 2 ... k 1 2 2 – show that left side 1+2+…k+1 = right side (k+1)(k+2)/2 – 1+2+…+k+1 = (1+2+…+k) + k+1 – sub from inductive hypothesis: k(k 1) (k 1) k(k 1) 2(k 1) 2 (k 1)(k 2) 2 2 2 Theorem 4.2.2 • Sum of the First n Integers – For all integers n≥1, n(n 1) 1 2 ... n 2 Example • Sum of the First n Integers – Find 2+4+6+…+500 • • • • Get in form of Theorem 4.2.2 (1+2+…+n) factor out 2: 2(1+2+3+…+250) sum = 2( n(n+1)/2 ), n = 250 sum = 2( 250(250+1)/2 ) = 62,750 – Find 5+6+7+8+…+50 • add first 4 terms 1+2+3+4 to problem then subtract back out after computation with 4.2.2 • 1+2+3+4+5+6+7+…+50 – (1+2+3+4) • (50 (50+1)/ 2) – 10 • =1,265 Sum of Geometric Sequence r n 1 1 r r 1 i0 n • Prove that , for all integers n≥0 and all real numbers r except 1. r 1 r • P(n): r 1 • Basis: r r r 11 1 • Inductive: (n=k) r r 1 r 1 • Inductive Hypothesis: (n=k+1) i n 1 n i i0 0 01 i i0 k 1 k i i0 k 1 r k 11 1 r k 2 1 r r 1 r 1 i0 i k 1 k r r i i0 i0 i r k 1 r k 1 1 k 1 r k 1 1 r k 1(r 1) r k 1 1 r k 2 r k 1 r k 2 1 r r 1 r 1 r 1 r 1 r 1 Theorem 4.2.3 • Sum of Geometric Sequences – For any real number r except 1, and any integer n≥0, r r r 11 n 1 n i i0 Examples • Sum of Geometric Sequences – Find 1 + 3 + 32 + … + 3m-2 r n 1 1 r r 1 i0 n i • Sequence is in geometric series, apply 4.2.3 directly 30 31 32 ... 3m 2 3m 21 1 3m 1 1 3 1 2 – Find 32 + 33 +… + 3m • rearrange into proper geometric sequence by factoring out 32 from sequence m 2 m 1 3 1 2 i • 32(1 + 3 + 32 + … + 3m-2) =3 3 3 1 i0