maths
sample files/cherry-2011-mathematical-induction-eitxsrhu.pdf Mathematical Induction William Cherry February 2011 These notes provide some additional examples to supplement the section of the text on mathe- matical induction. Inequalities. It happens that often in mathematics, the more freedom one has in creating a solution, the more difficult it is to solve a problem. Often the easiest problems to solve are those where there is really only one way to get to the solution. In particular, this means that it is often more difficult to prove an inequality than an equality. Because your textbook does not work through examples of how to use induction to prove inequalities and yet these can be some of the more difficult exercises, these notes are intended to provide some examples of using induction to prove inequalities. Proposition 1. For every n ∈ N, we have n2 + 6n+ 7 < 20n2.="" proof="" by="" induction.="" let="" p="" (n)="" be="" the="" proposition="" n2="" +="" 6n+="" 7="">< 20n2.="" base="" step.="" we="" check="" p="" (1),="" which="" says="" 12="" +6(1)+="" 7="">< 20(1)2.="" the="" left-hand-side="" is="" 14="" and="" the="" right="" hand="" side="" is="" 20,="" so="" p="" (1)="" is="" true="" and="" the="" base="" step="" is="" complete.="" induction="" step.="" assume:="" n2="" +="" 6n+="" 7="">< 20n2.="" show:="" (n+="" 1)2="" +="" 6(n+="" 1)="" +="" 7="">< 20(n+="" 1)2.="" we="" will="" begin="" with="" the="" left-hand-side="" of="" the="" inequality="" we="" want="" to="" show="" because="" this="" is="" the="" more="" “complicated”="" looking="" side:="" (n+="" 1)2="" +="" 6(n+="" 1)="" +="" 7="n2" +="" 2n+="" 1="" +="" 6n+="" 6="" +="" 7="" [multiply="" out]="(n2" +="" 6n+="" 7)="" +="" (2n+="" 7)="" [group="" terms="" to="" make="" use="" of="" our="" assumption]="">< 20n2="" +="" (2n+="" 7)="" [using="" our="" induction="" assumption]="20n2" +="" 2n+="" 7="">< 20n2="" +="" 40n+="" 7="" [since="" 2n="">< 40n]="">< 20n2="" +="" 40n+="" 20="" [since="" 7="">< 20]="20(n2" +="" 2n+="" 1)="" [factor="" out="" 20]="20(n+" 1)2.="" [factor]="" thus,="" (n+="" 1)2="" +="" 6(n+="" 1)="" +="" 7="">< 20(n+="" 1)2,="" which="" is="" what="" we="" needed="" to="" show.="" remark.="" when="" we="" do="" a="" proof="" like="" this,="" it="" is="" important="" that="" all="" of="" our="" inequalities="" go="" the="" “same="" way.”="" in="" this="" case,="" they="" were="" all="">< .="" we="" may="" not="" mix="">< and=""> . 1 Mathematical Induction 2 Proposition 2. For every natural number n ≥ 12, we have 5n < n!.="" proof="" by="" induction.="" base="" step.="" in="" this="" case,="" we="" only="" claim="" the="" inequality="" is="" true="" for="" n="" ≥="" 12,="" so="" that="" makes="" our="" base="" step="" n="12." thus,="" we="" need="" to="" check="" whether="" 512="">< 12!.="" using="" a="" calculator="" or="" computer="" (or="" a="" lot="" of="" patience),="" we="" determine="" that="" 512="244," 140,="" 625="" and="" 12!="479," 001,="" 600,="" and="" thus="" we="" see="" that="" the="" base="" step="" is="" true.="" induction="" step.="" assume:="" 5n="">< n!.="" show:="" 5n+1="">< (n+="" 1)!.="" we’ll="" start="" with="" the="" left-hand-side="" of="" what="" we="" are="" trying="" to="" show:="" 5n+1="5" ·="" 5n="" [re-write="" so="" we="" can="" use="" our="" assumption]="">< 5="" ·="" n!="" [since="" 5n="">< n!="" by="" our="" induction="" assumption]="">< (n+="" 1)="" ·="" n!="" [since="" n+="" 1=""> 5 (remember n ≥ 12)] = (n+ 1)!. [simplifying] Hence, 5n+1 < (n+="" 1)!="" as="" required.="" remark.="" this="" last="" example="" also="" shows="" the="" necessity="" of="" the="" base="" step.="" notice="" that="" the="" only="" thing="" we="" needed="" in="" the="" induction="" step="" was="" that="" n+="" 1=""> 5, so the induction step works as long as n > 5. However, 56 = 3125 and 6! = 720, so the proposition is not true for n = 6. We really need the base step too for our proof to be valid. Sometimes we might have to prove several inequalities in order to get to the one we want. For example, suppose we want to prove n3 < 2n.="" if="" we="" take="" a="" look="" at="" the="" induction="" step,="" it="" would="" go="" something="" like="" this:="" assume:="" n3="">< 2n.="" show:="" (n+="" 1)3="">< 2n+1.="" if="" we="" now="" start="" working="" with="" what="" we="" want="" to="" show,="" we="" get="" something="" like="" (n+="" 1)3="n3" +="" 3n2="" +="" 3n+="" 1="" [multiply="" out]="">< 2n="" +="" 3n2="" +="" 3n+="" 1.="" but,="" now="" we="" are="" kind="" of="" stuck.="" if,="" however,="" we="" somehow="" knew="" that="" 3n2="" +="" 3n="" +="" 1="">< 2n,="" we="" could="" continue:="" 2n="" +="" 3n2="" +="" 3n+="" 1="">< 2n="" +="" 2n="2" ·="" 2n="2n+1." well,="" we="" should="" then="" try="" to="" prove="" 3n2="" +="" 3n="" +="" 1="">< 2n,="" which="" we="" can="" also="" do="" by="" induction,="" after="" taking="" another="" detour.="" mathematical="" induction="" 3="" proposition="" 3.="" for="" each="" naturual="" number="" n="" ≥="" 6,="" we="" have="" 6n+="" 6="">< 2n.="" proof="" by="" induction.="" base="" step.="" when="" n="6," we="" have="" 6(6)="" +="" 6="42">< 64="26." induction="" step.="" assume:="" 6n+="" 6="">< 2n.="" show:="" 6(n+="" 1)="" +="" 6="">< 2n+1.="" now,="" 6(n+="" 1)="" +="" 6="6n+" 6="" +="" 6="">< 2n="" +="" 6="" [using="" our="" induction="" assumption]="">< 2n="" +="" 2n="" [since="" 6="">< 2n="" when="" n="" ≥="" 3]="2" ·="" 2n="2n+1," as="" was="" to="" be="" shown.="" proposition="" 4.="" for="" each="" natural="" number="" n="" ≥="" 8,="" we="" have="" 3n2="" +="" 3n+="" 1="">< 2n.="" proof="" by="" induction.="" base="" step.="" when="" n="8," we="" have="" 3(8)2="" +="" 3(8)="" +="" 1="217">< 256="28," and="" so="" the="" base="" step="" is="" true.="" induction="" step.="" assume:="" 3n2="" +="" 3n+="" 1="">< 2n.="" show:="" 3(n+="" 1)2="" +="" 3(n+="" 1)="" +="" 1="">< 2n+1.="" starting="" with="" the="" left-hand-side="" of="" what="" we="" need="" to="" show,="" we="" have="" 3(n+="" 1)2="" +="" 3(n+="" 1)="" +="" 1="3(n2" +="" 2n+="" 1)="" +="" 3n+="" 3="" +="" 1="3n2" +="" 6n+="" 3="" +="" 3n+="" 3="" +="" 1="(3n2" +="" 3n+="" 1)="" +="" (6n+="" 6)="" [re-group="" to="" apply="" induction="" assumption]="">< 2n="" +="" (6n+="" 6)="" [by="" our="" induction="" assumption]="">< 2n="" +="" 2n="" [by="" proposition="" 3]="2" ·="" 2n="2n+1," as="" required.="" we="" are="" now="" finally="" able="" to="" get="" to="" the="" inequality="" we="" wanted.="" proposition="" 5.="" for="" each="" natural="" number="" n="" ≥="" 10,="" we="" have="" n3="">< 2n.="" proof="" by="" induction.="" base="" step.="" when="" n="10," we="" have="" 103="1000">< 1024="210," mathematical="" induction="" 4="" and="" so="" the="" base="" step="" holds.="" induction="" step.="" assume:="" n3="">< 2n.="" show:="" (n+="" 1)3="">< 2n+1.="" starting="" with="" the="" left-hand-side,="" (n+="" 1)3="n3" +="" 3n2="" +="" 3n+="" 1="" [multiply="" out]="">< 2n="" +="" 3n2="" +="" 3n+="" 1="" [using="" our="" induction="" assumption]="">< 2n="" +="" 2n="" [by="" proposition="" 4]="2" ·="" 2n="2n+1," and="" so="" we="" are="" done.="" generalized="" strong="" induction.="" the="" method="" of="" proof="" by="" induction="" can="" be="" generalized="" as="" follows.="" suppose="" we="" have="" a="" proposition="" p="" (n)="" and="" suppose="" we="" want="" to="" prove="" that="" p="" (n)="" is="" true="" for="" all="" integers="" n="" such="" that="" n="" ≥="" m="" for="" some="" integer="" m.="" suppose="" we="" also="" prove="" the="" following:="" generalized="" base="" step:="" there="" exists="" an="" `="" ∈="" z="" such="" that="" p="" (j)="" is="" true="" for="" j="m,m+" 1,="" .="" .="" .="" ,="" `.="" strong="" induction="" step:="" for="" each="" k="" ∈="" z="" such="" that="" k="" ≥="" `,="" we="" have="" (p="" (m)="" ∧="" p="" (m+="" 1)="" ∧="" p="" (m+="" 2)="" ∧="" ·="" ·="" ·="" ∧="" p="" (k))="" ⇒="" p="" (k="" +="" 1).="" in="" analogy="" with="" my="" stairstep="" explanation="" in="" class,="" this="" goes="" as="" follows.="" for="" the="" generalized="" base="" step,="" suppose="" we="" can="" show="" that="" we="" can="" get="" to="" any="" of="" the="" first="" five="" stairs="" on="" the="" infinite="" stair="" case.="" now="" suppose="" that="" we="" can="" show="" that="" if="" we="" can="" get="" all="" the="" stairs="" before="" the="" k="" +="" 1-st="" step,="" then="" we="" can="" also="" get="" to="" k+1-st="" step.="" then="" we="" can="" climb="" all="" the="" stairs.="" imagine,="" for="" example,="" that="" in="" order="" to="" go="" up="" a="" stair,="" we="" need="" to="" both="" stand="" on="" the="" stair="" before,="" and="" use="" the="" assistance="" of="" a="" pole="" resting="" on="" the="" stair="" before="" that.="" in="" practice,="" strong="" induction="" often="" works="" as="" follows.="" we="" do="" a="" double="" base="" step,="" for="" example,="" we="" show="" p="" (1)="" and="" p="" (2)="" are="" true.="" then,="" for="" the="" induction="" step,="" we="" show="" that="" p="" (n−="" 1)="" and="" p="" (n)="" together="" imply="" p="" (n+="" 1).="" that="" is,="" we="" use="" the="" assistance="" of="" two="" previous="" stairs="" to="" help="" us="" climb="" to="" the="" next="" step.="" here="" is="" an="" example.="" proposition="" 6.="" for="" each="" natural="" number="" n,="" there="" exist="" natural="" numbers="" a="" and="" b="" such="" that="" 5n="a2" +="" b2.="" proof="" by="" strong="" induction.="" base="" step.="" we="" will="" do="" a="" double="" base="" step,="" allowing="" us="" to="" go="" two="" steps="" back="" in="" our="" induction="" step.="" for="" n="1," we="" can="" choose="" a="1" and="" b="2" and="" we="" have="" 51="5" =="" 1="" +="" 4="12" +="" 22.="" for="" n="2," we="" can="" choose="" a="3" and="" b="4," since="" 52="32" +="" 42.="" mathematical="" induction="" 5="" induction="" step.="" for="" this="" proof,="" instead="" of="" showing="" that="" p="" (n)="" implies="" p="" (n="" +="" 1),="" we="" will="" show="" that="" p="" (n="" −="" 1)="" implies="" p="" (n="" +="" 1).="" because="" we="" are="" “skipping="" over="" a="" step”="" each="" time,="" we="" need="" the="" double="" base="" step="" above.="" assume:="" there="" exist="" a="" and="" b="" in="" n="" such="" that="" 5n−1="a2" +="" b2.="" show:="" there="" exist="" c="" and="" d="" in="" n="" such="" that="" 5n+1="c2" +="" d2.="" we="" start="" with="" the="" left-hand-side,="" and="" write="" 5n+1="52" ·="" 5n−1.="" then,="" we="" use="" our="" induction="" assumption="" that="" 5n−1="a2" +="" b2.="" so,="" we="" then="" have="" 5n+1="52" ·="" 5n−1="52(a2" +="" b2)="52a2" +="" 52b2="(5a)2" +="" (5b)2.="" thus,="" we="" can="" choose="" c="5a" and="" d="5b" to="" get="" 5n+1="c2" +="" d2,="" and="" our="" proof="" is="" complete.="" fibonacci="" numbers.="" the="" fibonacci="" numbers="" are="" defined="" recursively="" as="" follows:="" f0="0," f1="1," and="" fn="Fn−1" +="" fn−2="" for="" n="" ≥="" 2.="" so,="" for="" instance,="" the="" fibonacci="" numbers="" start="" out="" 0,="" 1,="" 1,="" 2,="" 3,="" 5,="" 8,="" 13,="" 21,="" 34,="" 55,="" 89,="" 144,="" 233,="" .="" .="" .="" where="" the="" first="" two="" are="" 0="" and="" 1="" and="" each="" successive="" number="" is="" obtained="" by="" adding="" the="" previous="" two.="" problems="" involving="" fibonacci="" numbers="" are="" natural="" candidates="" for="" going="" backward="" two="" steps.="" proposition="" 7.="" for="" each="" n="0," 1,="" 2,="" 3,="" .="" .="" .="" ,="" we="" have="" fn="">< 2="" n.="" proof="" by="" strong="" induction.="" base="" step.="" we="" will="" verify="" the="" inequality="" for="" n="0" and="" n="1" for="" our="" base="" step.="" for="" n="0," we="" have="" f0="0">< 1="2" 0.="" for="" n="1," we="" have="" f1="1">< 2 = 2 1, and so we have 2="2" 1,="" and="" so="" we="">