COT3100 Summer 2001 Recitation on induction Solutions 07 12 2001 1 Use mathematical induction to prove that 3 divides n3 2n whenever n is a nonnegative integer We are going to prove by induction on n 0 that n3 2n is divisible by 3 Basis n 0 03 0 0 is divisible by 3 so the proposition holds for n 0 IH Assume that the proposition is true for n k where k is some integer k 0 In other words we assume that k3 2k is divisible by 3 i e k3 2k 3p p is an integer IS We need to prove that k 1 3 2 k 1 is divisible by 3 k 1 3 2 k 1 k3 3k2 3k 1 2k 2 k3 2k 3 k2 k 1 3p 3 k2 k 1 by IH Since both terms have factor 3 the sum is divisible by 3 So induction step is proved By Induction Principle the proposition is true for any n 2 Use induction to prove that 3 3 5 3 52 3 5n 3 5n 1 1 4 We are going to prove by induction on n 0 that the equality is true Basis n 0 LHS 3 RHS 3 50 1 1 4 3 So LHS RHS IH Assume that the proposition is true for n k where k is some integer k 0 In other words we assume that for some k 0 3 3 5 3 52 3 5k 3 5k 1 1 4 IS We need to prove that 3 3 5 3 52 3 5k 3 5 k 1 3 5 k 1 1 1 4 3 3 5 3 52 3 5k 3 5 k 1 3 5k 1 1 4 3 5 k 1 by IH 3 5k 1 1 4 3 4 5 k 1 4 3 5 5k 1 1 4 3 5 k 1 1 1 4 algebra So IS is proved and by Induction principle the formula is proved for any n 0 3 Prove that for any n 1 1 1 1 1 1 2 2 4 9 n n We are going to prove it by induction on n 2 Basis n 2 LHS 1 1 4 5 4 RHS 2 1 2 3 2 LHS RHS IH Assume that the inequality holds for n k where k is some integer k 2 i e we 1 1 1 1 assume that for some k 2 1 2 2 4 9 k k 1 1 1 1 1 2 2 2 k 1 k k 1 1 1 1 1 1 1 2 LHS 1 4 9 2 by IH 2 k k k 1 k 1 2 1 1 1 2 To prove inductive step it is sufficient to show that 2 k 2 k 1 k 1 1 1 1 1 We can note that k k 1 k k 1 since k k 1 k 1 2 IS We need to prove that 1 4 9 By rearranging the terms we can get what we need 1 1 1 2 k k 1 k 1 In this way the inductive step is proved By induction principle the inequality is true for any n 1 4 Harmonic numbers Hk k 1 2 3 are defined by H k 1 1 1 1 2 3 k n 2 1 3 1 3 3 3 H 2 1 RHS 1 and the proposition is 2 2 2 2 2 2 Use mathematical induction to prove that H 2n 1 Basis n 1 LHS H 21 true IH Assume that for n k where k is some integer k 1 the inequality is true i e H 2 k 1 k 2 k 1 By the given definition of harmonic function 2 1 1 1 1 1 1 1 k 1 H 2 k k k 1 we have H 2 k 1 1 k k 2 3 2 2 1 2 2 1 2 k 1 1 k 1 By IH we have H 2 k 1 1 k 2 2 1 2 1 1 1 k 1 To prove inductive step it is sufficient to show that k 2 2 1 2 IS We need to prove that H 2 k 1 1 In the left hand side we have the sum of 2 k 1 2 k 2 k 2 1 2 k terms and each term 1 1 1 k k 1 k k 2 s 2 2 2 1 1 1 1 k 1 2 k k 1 so that the total sum is k 2 2 1 2 2 We proved inductive step and by induction principle the inequality is true for all integer n 1 5 Prove by induction that for any integers a and b a b an bn where n is a positive integer n 1 We are going to prove by induction on n 1 that for any integers a and b an bn is divisible by a b By the definition of divisibility it is sufficient to prove that for any n 1 for any a and b there exists an integer m such that an bn m a b Basis n 1 a b 1 a b IH Assume that proposition is true for n k where k is some integer k 1 In other words we assume that for some k 1 and any a and b there exists an integer m such that ak bk m a b IS We need to prove that the proposition holds for n k 1 i e for any a b there exists some integer s such that ak 1 bk 1 s a b To reduce k 1 case to the case n k we consider the following identity ak 1 bk 1 a ak bk a bk bk 1 a ak bk bk a b By IH we have for these a and b some integer m such that ak bk m a b so a ak bk bk a b a m a b bk a b k 1 So a bk 1 a b a m bk a b s where s a m bk We proved IS and by Induction Principle the proposition is true for any n 1 6 A sequence of numbers an is defined recursively as follows a0 0 an 1 2 an 1 for n 0 Prove that an 2n 1 Proof by induction on n 0 that the recursively defined sequence satisfies the closed formula an 2n 1 Basis n 0 a0 0 that agrees with the formula a0 20 1 1 1 0 IH Assume that for n k k is an integer k 0 that the formula is correct i e ak 2k 1 IS We need to prove the formula for n k 1 i e that ak 1 2k 1 1 ak 1 2 ak 1 by recursive definition 2 2k 1 1 by IH 2k 1 2 1 2k 1 1
View Full Document
Unlocking...