COT3100 Summer’2001Recitation on induction (Solutions)07/12/20011. 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+35+352+… +35n = 3(5n+11)/4We are going to prove by induction on n 0 that the equality is true.Basis. n =0. LHS =3, RHS=3(50+11)/4=3. So, LHS=RHS.IH. Assume that the proposition is true for n=k, where k is some integer k0. In other words we assume that for some k0 3+35+352+… +35k = 3(5k+11)/4IS. We need to prove that 3+35+352+… +35k + 35(k+1) = 3(5(k+1)+11)/43+35+352+… +35k + 35(k+1) = 3(5k+11)/4 + 35(k+1) (by IH)= 3(5k+11)/4 + 345(k+1)/4 =3(5 5k+11)/4 = 3(5(k+1)+11)/4 (algebra)So, IS is proved and by Induction principle the formula is proved for any n 0.3. Prove that for any n >1nn121...914112We 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 assume that for some k 2 kk121...914112IS. We need to prove that )1(12)1(11...9141122kkkLHS= 222)1(112)1(11...91411kkkk, by IH.To prove inductive step it is sufficient to show that 112)1(1122kkkWe can note that 2)1(1)1(1111kkkkk, since k<k +1.By rearranging the terms we can get what we need, 111)1(12kkkIn 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 bykHk1...31211 .Use mathematical induction to prove that 212nHnBasis. n =1, LHS=23211221HH, RHS =23211 and the proposition 2323 is true. IH. Assume that for n =k, where k is some integer k 1, the inequality is true, i.e.212kHkIS. We need to prove that 21112kHk. By the given definition of harmonic function we have 121221...12121...12121...312111kkkkkkkHHBy IH we have 1221...121211kkkHkTo prove inductive step it is sufficient to show that 2121...1211kk.In the left hand side we have the sum of kkkk2)12(2221terms and each term12122121kkkks, so that the total sum is 2121221...12111 kkkk. 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 (ab) | (anbn), where n is a positive integer, n 1. We are going to prove by induction on n1, that for any integers a and b, (anbn) is divisible by (ab). 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 (anbn)=m(ab). Basis. n=1, (ab) = 1(ab).IH. Assume that proposition is true for n=k, where k is some integer, k1. In other words, we assume that for some k1 and any a and b there exists an integer m such that (akbk)=m(ab).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+1bk+1)=s(ab)To reduce k+1 case to the case n=k, we consider the following identity: ak+1bk+1= a(akbk)+a bkbk+1= a(akbk)+bk (ab)By IH we have for these a and b some integer m such that (akbk)=m(ab), so:a(akbk)+bk (ab) =a m(ab) + bk (ab)So, ak+1bk+1= (ab) (a m+ bk)= (ab) 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=2an+1, for n0 Prove that an=2n1.Proof by induction on n0, that the recursively defined sequence satisfies the closed formula an=2n1.Basis. n=0, a0=0, that agrees with the formula a0= 201=11=0.IH. Assume that for n =k, k is an integer k0, that the formula is correct, i. e. ak=2k1.IS. We need to prove the formula for n =k+1, i.e . that ak+1=2k+11.ak+1=2ak+1 (by recursive definition) = 2(2k1)+1 (by IH) =
View Full Document
Unlocking...