University of Illinois at Urbana Champaign Fall

profil-urra-2012

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

3 pages

English

Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

A propos
Informations
Extrait

Description

University of Illinois at Urbana-Champaign Fall 2006 Math 444 Group E13 1. Prove by induction that for all n ≥ 1 one has 1 12 + 1 22 + . . . + 1 n2 < 2 . Correction. First, following the hint, let us call P (n) the property 1 12 + 1 22 + . . . + 1 n2 ≤ 2? 1 n . Then P (1) is the assertion 1 ≤ 1, so P (1) is true. Now, assume that n ? N is such that P (n) is true. We wish to deduce from this that P (n+1) is also true. We have 1 12 + 1 22 + . . . + 1 (n + 1)2 = 1 12 + 1 22 + . . . + 1 n2 + 1 (n + 1)2 ≤ 2? 1 n + 1 (n + 1)2 (?) by the induction hypothesis. To obtain what we want, it is therefore enough to prove that? 1 n + 1 (n + 1)2 ≤ ? 1 n + 1 , which is equivalent to 1 (n + 1)2 ≤ 1 n ? 1 n + 1 .

urbana-champaign fall

since both maps

k? ?

induction hypothesis

induction theorem enables

Sujets

Mathematical induction

Informations

Publié par	profil-urra-2012
Nombre de lectures	98
Langue	English

Extrait

n≥ 1
1 1 1
+ +...+ < 2 .
2 2 21 2 n
1 1 1 1
P(n) + +...+ ≤ 2− P(1)
2 2 21 2 n n
1≤ 1 P(1)
n∈N P(n) P(n+1)
1 1 1 1 1 1 1 1 1
+ +...+ = + +...+ + ≤ 2− + (∗)
2 2 2 2 2 2 2 21 2 (n+1) 1 2 n (n+1) n (n+1)
1 1 1
− + ≤−
2n (n+1) n+1
1 1 1
≤ −
2(n+1) n n+1
1 1 1 1 1 1
− = − ≥
2n n+1 n(n+1) n n+1 (n+1)
1 1 1 1
+ +...+ ≤ .
2 2 21 2 (n+1) n+1
P(n+1) P(n) P(1)
P(n) n∈N
P(n)
n P(1)
P(n) P(n+1) n+1
n
n
n+1 P(n+1)
P(n) n
P(1)
P(1) P(2)
n ≥ 2 P(n) ⇒ P(n + 1)
P(n) n≥ 2
X,Y,Z f: Y →Z g: X →Y
• f◦g
−1• (f◦g)
−1 −1 −1• (f◦g) =g ◦f
itisysThenes.encilsyrangeertTpropsecondtheNotice,callsetsussholetlt,othershinobThisallpropvthatesforthatbijectivthevwingthenfollopFirst,allCorrection.pissametrueencilsasrstsoinonareassamehasareoneisallWforsiisyp;wsinceofthatequivnductionvistoalsotruetrue,ytheysithenduction;theoremaenablessausrsttotrue).concludethatthatcoloriinyencibeewiisintrueandfogroupenotallreunionvoProer,1.of.w2.pLettousbprohvTewhatbisyWhatinduction?thatquestionsall,thatisthethatpthat,encilissthisinonethewwoforldandareatheotherssameone)colorsame:isdenoteabtheyoneE13thatGroup.e,444areMath(atheonepropthiserttheythe"inthisanfalse,ycasegroupofofand2006happtencils,sotheygarepallrstthesamesamallethecolor".reThendoallthatFinestthevraie.sameLetouswnoforwtheassumethethatseeaignalsomphaUrbana-Chacorrectthappisetrvue,isandthetry3.toSinceproevoeethatt,awllinoismaps.ItheoftoUniversityisassertiontalsenohtrue.",GivthatenNoathatgroupreasoningofwsisifthatdeduceobtaintrue,pfromencils,istak:etakoneaofathemoneathewencils,asaythat:lbthey(i.e,theotherinductionarehtheypcolorothisthetrue.sis,akingtheweypotherencilsencil,remainingagainareysallthethe(isamethecolor.one)Putthethatcolorpgain,encilThenbacsak,thatandimpliestakallepaarewsamea:yisanotherviouslyonesince:thatthethewgroupppencilslsremainingthearegroupagainvtheemsameycolortersection,;knoconsequennthattlythe,encilsallthethegroup(*),thetocolorinthatppencilsinaresecondtheasamethecolor,colorsoeskimplybacallthisencilsputtingthe;ofisgroupstrue.theThereforecsuclhr.thathoisevisthattruethatforindeedallprotrue.of,factandthatwee,aretrue.doneewiistherfectlythe;projustof.ensWhatbisuseless,thenceWeoblemywithfalsetheallrinductione.asoninLetgothesis.ab.oveb?threeCorrection.andTheobtainfactwthat,eanwishitisttrueoiseclear,thereforesoisthedomainproblemenoughmtoustwhatbitse?somewhereSameelsforeal;islowhicok.atProhoewso"true.thew,probassumeoevetheapr.is• f◦g x g
g(x) f f◦g g X
f◦g Z z∈Z
f y∈Y z =f(y) g x∈X y =g(x)
z =f(g(x)) = (f◦g)(x) z f◦g
Z⊂R(f◦g) f,g
R(f◦g) =Z
−1• (f◦g) f◦g Z
−1(f◦g) f◦g X
−1• (f◦g) z∈Z x∈X
−1x = (f ◦g) (z)⇔ (f ◦g)(x) = z f
−1 −1 −1g f◦g (f◦g) =g ◦f
−1 −1 −1 −1 −1 −1z∈Z (f◦g)(g ◦f (z)) =z (f◦g)(g ◦f (z)) =f(g(g (f (z))))
−1 −1 −1 −1g(g (y)) = y y ∈ Y g(g (f (z))) = f (z)
−1 −1 −1 −1 −1 −1f(g(g (f (z)))) =f(f (z)) =z (f◦g) =g ◦f
X,Y,Z f: X →Y g: Y →Z
• (g◦f )⇒ (f )
• (g◦f )⇒ (g )
0 0 0• g◦f x,x ∈X f(x) =f(x ) g(f(x)) =g(f(x ))
0 0(g◦f)(x) = (g◦f)(x ) g◦f x = x
f
• g◦f z ∈ Z y ∈ Y z = g(y)
g◦f x∈X z = (g◦f)(x) =g(f(x)) y =f(x)
z =g(y) g
f(x) = x x ∈ R g(x) = 0
x∈R f g◦f f(x) = 0 x∈R g(x) =x
x∈R g g◦f
2f,g:R→R f(x) =x g(x) =x+2 h =f◦g
• h(R) h(E) E ={x∈R: 0≤x≤ 1}
−1 −1• h (F) h (G) F = (1,+∞) G ={x∈R: −2≤x≤ 4}
2• x∈R h(x) = (x+2) h(x)≥ 0 x h(R)
√2[0,+∞) y≥ 0 x y = (x+2) x = y−2
y =h(x) y∈h(R) h(R) = [0,∞)
2x∈E 0≤x≤ 1 2≤x≤ 3 4≤h(x) = (x+2) ≤ 9 h(E)⊂ [4,9]
√
y∈ [4,9] x = y−2∈ [0,1] =E y =h(x) h(E) = [4,9]
−1 2• x∈h (F)⇔h(x)∈F ⇔ (x+2) > 1⇔|x+2|> 1⇔x+2> 1 x+2<−1
−1 −1x∈h (F)⇔x>−1 x<−3 h (F) = (−∞,−3)∪(−1,+∞)
−1 2x∈h (G)⇔−2≤ (x+2) ≤ 4⇔|x+2|≤ 2⇔x∈ [−4,0] .
−1h (G) = [−4,0]
f:N→N g:N→N
(
k k
2∀k∈N f(k) = 2k g(k) = .
k+1 k2
sincenotforareallforinclusionallfunctionsassertionsherselarlyvthisanddomainconThistheisthat.seeitovTofforthatawl6.lsetto..oneisto.onThendenesthatdenedisdomainone-to-onerangebut.esthatveprosucisThenot.toSimilarlymaps,case,ifhonebsetsifsbthi.andw,tonkbtaibijectivfor.alltooelyethenwfollandmap,thatLettingrange.itthatdomainhdenitionsucoffororallTherefore,someisexistsequalitiesthereThe,onthenistyieldsisit,onoftoe,but.thaisw;knoelongsisofnot.domain5.oinLetdomaineenwthat,hasononeothesis,ypthat,hhabve,the,functionshecdened).bthaty,theoyurbis;vthatifhthatsuc:,wingsomeyndandto.tThisan,wisetheW;.,Letis.mapping,generalanpic.anddenitionto,a.vonandDeterminevisThisthatthew,noorandwAssumethatone-to-one.thatistherethatsince,sucwhereto,emethovonpro.tovenoughsimplyisthethiseandbij,bt,thaTherefore,impliesdomainonin.domainassumptiontheDeterminethatOurare.eordsbwtootherwhicinofandis,denition,eisvohameanseyw;,OnewherehasThen,.Similarlythatifhforsuctheneebvleteandproandenoughone-to-one,soisitthatthatAssumeandCorrection.c?Therefore,neraleeisgimpliesinwhictrueandassertionsTherefersere.assumptionCorrection.ovdueWfunctioneConhaersv,e,aforthisallfactcon(ThetheandArerelation,,o.thetobon,toisonTheone-to-oneisone-to-one.:impliesassertionssowingof.theThereoffo.r,e,simifolloisthesoeofvtheProof.theforerseallinfunctionsof,ByandTherefore,thisofprothevconsequenceesisthaterseeconbthe,,andesis.aprosubset.ofrangesinsetsothreeusegivbtogether.oCo;nmeansvtersely.,hpicexistskto,someisLet;4.h.some;therew.esamewdanthattistoThen,ndletthatesucproh;thatisfactrangethethatofknoofwproectivthearenishesoth;Sinceii.etofistheclearsimplythatofhthewhicthat,therefore,yieldsofthis.;Letistoabsoandlsucutionandofbthattheequation,denedsoythatthethatelongsoh,tsallpforandmapping,theandofersethevByinCorrection.,evtrueletinanifofisdenitiondd.k• f g
• f◦g g◦f
• f f(k) k f
0 0 0 0f k,k ∈N f(k) =f(k )⇔ 2k = 2k ⇔k =k
g g(1) =g(2) = 1
k∈N g(2k) =k k∈R(g)
k
• f◦g g k g(k) =
2
k k +1
f◦g(k) =f(g(k)) = 2 =k k g(k) = f◦g(k) =k +1 f◦g(k)
2 2
k f◦g f◦g(1) = 2 =f◦g(2)
f◦g
f(k)
g◦f f(k) = 2k k g(f(k)) = =k
2
g◦f
g◦f(n) = n n g f
whetherwto.othatctoa:sthesev(boecause-oneofisthebwtheaey(forquestionforis;dened)not:thaifto.samealllisisevten,obthenoth;wtotoon,one-to-one,notisfurthermoreifComputeDetermineand,nesoarethatnetheComputingrangeisofone-to-one,doItesennot,concleartainforanonyhand,oitddthatinisteger.andOnthatthathenototherecause;allifethasisisono;dd,,then.onecomputehand,Tis.one-to-onedetermibsoectheyaisallodistinguish-to,either.sotforsoeeasierus,one-to-oneonnotCorrection.isisenevfunctionforThehas.sotooneisthatbijection.allthisecausetheto,haracterizationisbijectionsithe;admittingusnisvvioustheotherhereOnforballone-to-oneneedon(wNoticeeherealreadyeknewvthat.;onwhbyis?),forsoinstance)thatyeneitherwnor,.aThisComparemeanswiththatcforofallas,functionssoaecauseinbersefunction.What'sisdierenceev?en

Univers
Ebooks
Livres audio
Presse
Podcasts
BD
Documents

University of Illinois at Urbana Champaign Fall

Mathematical induction

YouScribe

Le catalogue

Le service

Les conditions