Introduction f Abstract description of induction a f n P n ...

1 PROOFS BY INDUCTIONPER ALEXANDERSSONI ntroductionThis is a collection of various proofs using induction . I have tried to includemany of the classical problems, such as theTower of Hanoi, theArt gallery problem,Fibonacciproblems, as well as other traditional examples. The problems areorganized by mathematical for the reader:When you are reading the proofs or better, trying towrite one yourself identify the following parts of the proof :The base case,theinduction hypothesis,where the hypothesis is usedandwhere properties given to youare used. For example, if you prove things about Fibonacci numbers, it is almost aguarantee that you have to use the recursionfn=fn 1+fn 2somewhere, whichis an essential property of the Fibonacci and suggestions are welcome description of inductionThe simplest application of proof by induction is to prove that a statementP(n)is true for alln= 1,2,3.

2 For example, The numbern3 nis divisible by6 The numberanis equal tof(n) and There aren!permutations ofnelements aresuch statements. induction usually amounts to proving thatP(1)is true, and thenthat the implicationP(n) = P(n+ 1). The principle of mathematical inductioncan formally be stated asP(1)andP(n) = P(n+ 1)for alln 1implies thatP(n)is true for alln induction is similar, but where we instead prove the implicationP(1) P(2) P(n) = P(n+ 1).(1)However, if we define introduce the new statementQ(n)asQ(n):=P(1) P(2) P(n),then(1)is equivalent toQ(n) = Q(n+ 1). Thus, strong induction is notreally different from usual induction , other than that the inductive hypothesis has aparticular textbooks introducing highlights the statementP(n)explicitly. This is apedagogical tool which is used to make the structure clearer.

3 However, proofs byinduction in the wild do not explicitly use the notationP(n), the statement issimply written out. In my experience, it is easy to confuse thestatementP(n)withtheformulaone is asked to prove. For example, The equalityan=f(n)holds. is the statementP(n), andf(n)is the actual : 8th August 2020,09 and productsProblem. 1 Show that forn 1, we have(a)n k=1k=n(n+ 1)2(b)n k=1(2k 1) = 1(a):We first check the base case,n= 1. The sum is1and the formula evaluates to1as well, so we are hypothesis:Assume that for somen 1we haven k=1k=n(n+ 1) add(n+ 1)on both sides of this relation and getn+1 k=1k= (n+ 1) +n(n+ 1) right hand side can now be rewritten asn+1 k=1k=[n+ 1]([n+ 1] + 1) , we have proved that if the formula holds forn, it holds forn+ 1. By theprinciple of mathematical induction , the identity is true for all integersn 1.

4 (b):We first check the base case,n= 1. Both sides evaluates to1, so we are hypothesis:Assume that for somen 1we haven k=1(2k 1) = add2(n+ 1) 1on both sides of this relation and getn+1 k=1(2k 1) = 2(n+ 1) 1 + right hand side can now be rewritten asn+1 k=1(2k 1) = [n+ 1] , we have proved that if the formula holds forn, it holds forn+ 1. By theprinciple of mathematical induction , the identity is true for all integersn 2 Show that forn 1, we have(a)n k=1k2=n(n+ 1)(2n+ 1)6(b)n k=1k(k+ 1) =n(n+ 1)(n+ 2)3 PROOFS BY INDUCTION3 Solution. 2(a):We first check the base case,n= 1. Both sides evaluates to1, so we are hypothesis:Assume that for somen 1we haven k=1k2=n(n+ 1)(2n+ 1) add(n+ 1)2on both sides of this relation and getn+1 k=1k2= (n+ 1)2+n(n+ 1)(2n+ 1) right hand side can now be rewritten asn+1 k=1k2=[n+ 1]([n+ 1] + 1)(2[n+ 1] + 1) , we have proved that if the formula holds forn, it holds forn+ 1.

5 Hence, theidentity is true for all integersn 1.(b):We first check the base case,n= 1. Both sides evaluates to2, so this is hypothesis:Assume that for somen 1we haven k=1k(k+ 1) =n(n+ 1)(n+ 2) add(n+ 1)(n+ 2)on both sides of this relation and getn+1 k=1k(k+ 1) = (n+ 1)(n+ 2) +n(n+ 1)(n+ 2) right hand side can now be rewritten asn+1 k=1k(k+ 1) =(n+ 1)(n+ 2)(n+ 3) , we have proved that if the formula holds forn, it holds forn+ 1. Hence, theidentity is true for all integersn 3 Prove that(a)n j=11j(j+ 1)=nn+ 1(b)n k=1( 1)kk2=( 1)nn(n+ 1)2(c)n k=1k k! = (n+ 1)! 3(a):Base case,n= 1, where both sides evaluates hypothesis:Assume that for somen 1we haven j=11j(j+ 1)=nn+ add1/((n+ 1)(n+ 2))on both sides of this relation and getn+1 j=11j(j+ 1)=1(n+ 1)(n+ 2)+nn+ ALEXANDERSSONSome algebra in the right hand side givesn+1 j=11j(j+ 1)=n+ 1n+ , we have proved that if the formula holds forn, it holds forn+1, and inductionthen tells us that the formula is true for alln 1.

6 (b):Base case,n= 1, where both sides evaluates to hypothesis:Assume that for somen 1we haven k=1( 1)kk2=( 1)nn(n+ 1) add( 1)n+1(n+ 1)2on both sides:n+1 k=1( 1)kk2= ( 1)n+1(n+ 1)2+( 1)nn(n+ 1) simplifies ton+1 k=1( 1)kk2=( 1)n+1(n+ 1)(n+ 2) , we have proved that if the formula holds forn, it holds forn+1, and inductionthen tells us that the formula is true for alln 1.(c):The base casen= 1says1 1! = 2! 1, which is true. Assume that the formulaholds for a particular value ofn 1. We add(n+ 1)(n+ 1)!on both sides and getn k=1k k! + (n+ 1)(n+ 1)! = (n+ 1)! 1 + (n+ 1)(n+ 1)! n+1 k=1k k! = (n+ 1)![1 + (n+ 1)] , we rewrote the sum and the right hand side a bit. Now we note that this issimplyn+1 k=1k k! = (n+ 2)! 1,which is the formula forn+ 1. This completes the 4 Formula for geometric sum. Supposea6= 1and prove thatn j=0aj=an+1 1a BY INDUCTION5 Solution.

7 4 Base casen= 0: The left hand side is justa0= 1. The right hand side isa 1a 1= 1as now that the formula holds for a particular value ofn. We wish to provethatn+1 j=0aj=an+2 1a is equivalent to provingan+1+n j=0aj=an+2 1a 1,and using the induction hypothesis, the sum in the left hand side can be expressedusing the formula. Thus, we need to provean+1+an+1 1a 1=an+2 1a both sides witha 1gives(a 1)an+1+an+1 1 =an+2 1,which is easily seen to be true. Hence, the formula above holds for alln 5 Prove thatn!>2nforn 5 The base casen= 4states that4!>24, and we see that24>16so this is the inequality holds for a particularn 4, so thatn!> both sides with(n+ 1), and we then know(n+ 1)n!>(n+ 1)2n (n+ 1)!>(n+ 1) thatn+1>2, so for sure(n+1)2n>2 2n= 2n+1. We can therefore concludethat(n+ 1)!>2n+ , we have proved thatn!>2n (n+ 1)!

8 >2n+1whenevern 4and so the inequality holds for all integersn 6 Prove that(a)n j=2(1 1j2)=n+ 12n,(b)n j=1j2j+ 1=n!n+ ALEXANDERSSONS olution. 6(a):Base case isn= 2. The left hand side is just1 14while the right hand side is34, so both sides are now thatn j=2(1 1j2)=n+ 12nfor somen multiplying both sides with1 1(n+1)2we getn+1 j=2(1 1j2)=(1 1(n+ 1)2)n+ 12n=(n+ 1)2 1(n+ 1)2n+ 12n=(n+ 1)2 12n(n+ 1)=(n+ 1) + 12(n+ 1).Thus, the induction hypothesis impliesn+1 j=2(1 1j2)=(n+ 1) + 12(n+ 1),which is the formula for the nextn . This concludes the proof .(b):Same idea, we check the base casen= 1, and see that both sides are equalto12. Suppose the formula holds for somen 1, and multiply both sides with(n+1)2(n+1)+1. The result we get isn+1 j=1j2j+ 1=(n+ 1)2(n+ 1) + 1n!n+ 1=n!(n+ 1)n+ 2=(n+ 1)!n+ 2which is what we want to 7 Prove thatn j=1(1 +1j2) n+ 7 The inequality is certainly true forn= 1, as we get3/2<2.

9 Suppose the inequalityis true for somen 1. Multiply both sides with1 + (n+ 1) 2and we getn+1 j=1(1 +1j2) (n+ 1)(1 + (n+ 1) 2).PROOFS BY INDUCTION7 Thus, we conclude thatn+1 j=1(1 +1j2) (n+ 1) +1n+ 1< n+ 2since for sure1n+1<1. We conclude that the induction hypothesis impliesn+1 j=1(1 +1j2)< n+ 2and we are 8 Prove thatn k=11k2< : Prove the stronger statement that the left hand side is less than2 8 This is an example where it is sometimes easier to prove a stronger result. The basecasen= 1is hypothesis:Letn 1and supposen k=11k2<2 (n+ 1)2on both sides. We then getn+1 k=11k2<2 1n+1(n+ 1)2= 2 (n+ 1)2 nn(n+ 1) note that2 (n+ 1)2 nn(n+ 1)2= 2 n2+n+ 1n(n+ 1)2<2 n(n+ 1)n(n+ 1)2= 2 1n+ 1where the inequality comes from removing the1in the numerator. Thus,n+1 k=11k2<2 1n+ 1and we are 9 Try to prove thatn k=12k 12k<1 you fail, try to prove the stronger result that the left hand side is less than orequal to1 3n+ 9 The base casen= 1is easy to verify, we find that both sides are equal now that n 1k=12k 12k 1 3(n 1)+1.

10 We then have thatn k=12k 12k=(n 1 k=12k 12k)2n 12n 1 3(n 1) + 12n 12n8P. ALEXANDERSSON where we have used the induction hypothesis for the product in the middle finish the proof , we must show that1 3(n 1) + 1 2n 12n 1 3n+ denominators gives the equivalent inequality(2n 1) 3n+ 1 2n 3n can now square both sides (as squaring of non-negative numbers preserveinequalities)(2n 1)2(3n+ 1) (2n)2(3n 2).Hence, it is enough to prove that0 (2n)2(3n 2) (2n 1)2(3n+ 1).But the right hand side simplifies ton 1, and sincen 1, we can be sure thatn 1 0, and we are recap,n k=12k 12k 1 3(n 1) + 12n 12nby using the induction hypothesis on the firstn 1terms in the product. Then, weproved that1 3(n 1) + 12n 12n 1 3n+ 1by the argument above, so together,n k=12k 12k 1 3n+ , it is straightforward to see that1 3n+1<1 3n, as we make the denominatorsmaller.