Ako urobiť indukčné dôkazy?
V „slabom“ indukčnom dôkaze v konečnom dôsledku hľadáte spojenie medzi P (k) a P (k + 1), aby ste dokázali, že váš návrh je pravdivý.
Matematická indukcia je metóda matematického dokazovania založená na vzťahu medzi podmienenými tvrdeniami. Začnime napríklad podmienečným vyhlásením: „Ak je nedeľa, budem sledovať futbal.“ Môžete urobiť nasledujúce vyhlásenie, že: „Ak sledujem futbal, objednám si jedlo so sebou.“ Na toto tvrdenie by ste mohli nadviazať ďalším: „Ak si objednávam odvoz, nebudem variť.“ Z nich by ste mohli platne usúdiť, že: „Ak je nedeľa, nebudem variť “, pretože je tu logický vzťah medzi týmito podmienečnými vyhláseniami. Ak dokážete, že prvé tvrdenie v reťazci implikácií je pravdivé a každé tvrdenie implikuje ďalšie, prirodzene z toho vyplýva, že aj posledné tvrdenie v reťazci je pravdivé.To je ako funguje matematická indukcia a nasledujúce kroky budú ilustrovať, ako vytvoriť formálny indukčný dôkaz.
Metóda 1 z 2: použitie „slabej“ alebo „bežnej“ matematickej indukcie
- 1Posúďte problém. Povedzme, že budete požiadaní o výpočet súčtu prvých „n“ nepárnych čísel, zapísaných ako [1 + 3 + 5 +... + (2n - 1)], indukciou. (Posledný výraz tu pochádza zo skutočnosti, že ak zdvojnásobíte akékoľvek číslo a potom od tejto hodnoty odčítate 1, výsledné číslo bude vždy nepárne.) Najprv si môžete všimnúť, že súčet po sebe idúcich nepárnych čísel sa zdá, že má určitý vzorec. (napr. 1 + 3 = 4; 1 + 3 + 5 = 9; 1 + 3 + 5 + 7 = 16; 1 + 3 + 5 + 7 + 9 = 25). Zdá sa, že súčet je počet nepárnych čísel, ktoré pridávate, na druhú, nie? Teraz, keď máme predstavu o vzore, ktorý tu hráme, môžeme začať s dokazovaním.
- 2Uveďte vlastnosť, ktorá bude dokázaná pomocou indukcie. V našom prípade sme si všimli vzor vzťahujúci sa k súčtu prvých „n“ nepárnych čísel. Na dokončenie úlohy, ktorá nám bola priradená (tj. Výpočet súčtu prvých „n“ nepárnych čísel), by sme si skutočne mohli nájsť čas na zapísanie všetkých nepárnych čísel, počínajúc číslom 1 až po „n“, a sčítať ich hore. Existuje však jednoduchší spôsob. Na základe toho, čo sme pozorovali pri prvých niekoľkých súčtoch, ktoré sme urobili, by sme mohli ponúknuť túto vlastnosť, ktorú sa pokúsime dokázať prostredníctvom indukcie:
- 1 + 3 +... + (2n - 1) = n^2
- Túto vlastnosť budeme označovať ako P (n), pretože „n“ je premenná, ktorú sme použili vyššie.
- Znamienko rovnice na ľavej strane predstavuje súčet prvých „n“ nepárnych čísel začínajúcich 1.
- 3Pochopte koncept matematickej indukcie. Je užitočné uvažovať o indukcii z hľadiska domina, ktoré pripomína „reťazec implikácií“ diskutovaný v úvode vyššie. Myslite na každú hodnotu „n“ vo vyššie uvedenej vlastnosti, P (n), ako jednotlivé domino, usporiadané do radu. Ak dokážeme, že P (1)-prvá hodnota v reťazci-je pravdivá, znamená to, že môžeme prevrátiť prvé domino. Ďalej, ak predpokladáme, že je možné prevrhnúť akékoľvek jedno domino (tj. P (n) platí pre ľubovoľnú ľubovoľnú hodnotu „n“), a za tohto predpokladu, že je možné prevrhnúť aj nasledujúce domino (tj. (n + 1) je tiež pravda), to znamená, že môžeme prevrhnúť všetky domino s naším uvedeným majetkom. To znamená, že vlastnosť je vo všetkých prípadoch pravdivá a svoj cieľ sme dosiahli indukciou.
- 4Dokážte, že platí základný prípad vlastníctva. „Základný prípad“ pre konkrétnu vlastnosť je nejaká malá hodnota, ktorá ukazuje, že prvý výrok o vlastnosti platí. V tomto prípade použijeme „1“, pretože toto je prvé nepárne číslo a ľahko sa s ním pracuje. Ak platí vlastnosť pre základný prípad, ukážeme, že dokážeme prevrátiť prvé domino a môžeme prejsť na ďalší krok.
- P (1): 1 = 1^2
- P (1): 1 = 1 (Platilo, sme dobrí. Prvé domino dole.)
- 5Uveďte induktívnu hypotézu. Ďalší krok indukcie zahŕňa vytvorenie predpokladu. V našom prípade budeme predpokladať, že pre nejakú ľubovoľnú hodnotu "n"-povedzme "k"-že tvrdenie je pravdivé. To znamená, že veríme, že náš majetok bude držať bez ohľadu na hodnotu použitú pre „n“. Ak by to nebola pravda, naša vlastnosť (tj. Naše riešenie pôvodného problému výpočtu súčtu prvých „n“ nepárnych čísel) by nemalo veľké využitie. Aj keď sme zatiaľ nič nedokázali, tento predpoklad je dôležitý a má nasledujúcu formu:
- P (k): 1 + 3 +... + (2k - 1) = k^2
- Pamätajte si, že v dôkazoch predpokladáme, že je to pravda (tj. Môžeme prevrhnúť akékoľvek jednotlivé domino v reťazci).
- 6Dokážte, že indukčná hypotéza platí pre ďalšiu hodnotu v reťazci. Inými slovami, predpokladáme, že P (k) platí, a pomocou tohto predpokladu sa pokúsime dokázať, že platí aj P (k + 1). Ak to dokážeme, dokázali sme, že naša teória je platná pomocou indukcie, pretože ak zhodenie jedného domina (za predpokladu, že P (k) je pravdivé) zhodí ďalšie domino (pomocou tohto predpokladu, dokázanie P (k + 1) je tiež pravda), všetky domino padne a náš majetok sa preukáže ako platný. Skúsme to teda:
- P (k): 1 + 3 +... + (2k - 1) = k^2 je pravda.
- P (k + 1): 1 + 3 +... + (2k - 1) + (2 (k + 1) - 1) = (k + 1)^2
- Kurzívová časť vyššie na ľavej strane rovnice predstavuje sčítanie ďalšieho nepárneho členu v poradí, k + 1. Ak dokážeme, aby sa ľavá strana rovnala pravej strane, budeme mať podarilo.
- Z nášho predpokladu, vieme, že un-kurzívou časť nad equals k ^ 2, tak sa poďme urobiť, aby výmena.
- P (k + 1): k^2 + (2 (k + 1) - 1) = (k + 1)^2
- P (k + 1): k^2 + 2k + 1 = (k + 1)^2
- P (k + 1): (k + 1)^2 = (k + 1)^2
- 7Záver, že vlastnosť je platne dokázaná matematickou indukciou. Použitím malej algebry sme dokázali, že naša vlastnosť platí nielen pre ľubovoľnú hodnotu „n“, ale aj pre hodnotu nasledujúcu po tejto hodnote. Ukázali sme, že P (1) je pravdivá, za predpokladu, že P (k) je pravdivých, a dokázali sme, že na základe tohto predpokladu je pravdivý aj P (k + 1). Aby sme použili našu pokračujúcu domino analógiu, úspešne sme zrazili prvé domino a ukázali sme, že náš majetok má nejakú hodnotu. Potom, za predpokladu, že by bolo možné prevrhnúť ľubovoľné domino v reťazci, dokázali sme, že to nevyhnutne zrazí ďalšie domino, ad infinitum vo zvyšku reťazca. Ukázali sme teda, že naša vlastnosť platí vo všeobecnosti, a úspešne sme ukončili náš dôkaz matematickou indukciou.
Rovnako ako predtým, prvým krokom v každom indukčnom dôkazu je dokázať, že základný prípad platí.
Metóda 2 z 2: pomocou „silnej“ alebo „úplnej“ matematickej indukcie
- 1Pochopte rozdiel medzi týmito dvoma formami indukcie. Vyššie uvedený príklad je takzvanou „slabou“ indukciou, pomenovanou tak nie kvôli rozdielu v kvalite medzi týmito dvoma indukčnými metódami, ale skôr na ilustráciu rozdielu medzi tým, čo sa predpokladá v indukčnej hypotéze každého druhu dôkazu. Tieto dve dôkazové techniky sú v skutočnosti ekvivalentné, len je niekedy potrebné v induktívnej hypotéze predpokladať viac, aby sa dôkaz dokázal. Aby sme sa vrátili k našej dominovej analógii, niekedy váha predpokladu P (k) je pravdivá, nie je dostatočná na to, aby zhodila domino reprezentované P (k + 1). Niekedy musíte byť schopní zraziť všetko domino pred ním, aby dokázal, že váš návrh platí.
- 2Uveďte návrh, ktorý sa má preukázať silnou indukciou. Aby sme to ilustrovali, zvážme iný príklad. Povedzme, že sa od vás požaduje, aby ste dokázali pravdivosť tvrdenia, že všetky celé čísla väčšie ako 1 je možné zapísať ako súčin prvočísel.
- Rovnako ako predtým budeme tento návrh označovať ako P (n), kde „n“ je číslo, ktoré je možné vyjadriť ako súčin prvočísel.
- Pretože hovoríme o všetkých celých číslach väčších ako 1, „n“ bude musieť byť väčšie alebo rovné 2.
- Nezabudnite, že prvočíslo je kladné celé číslo väčšie ako 1, ktoré je možné rozdeliť iba bezo zvyšku a 1.
- 3Dokážte, že základné puzdro platí. Rovnako ako predtým, prvým krokom v každom indukčnom dôkazu je dokázať, že základný prípad platí. V tomto prípade použijeme 2. Pretože 2 je prvočíslo (deliteľné iba 1 a 1), môžeme dospieť k záveru, že základný prípad platí.
- 4Uveďte (silnú) induktívnu hypotézu. Tu je rozdiel medzi „slabou“ a „silnou“ indukciou najjasnejší, pretože tento krok je jediným rozdielom medzi týmito dvoma formami indukčného dôkazu. Induktívna hypotéza pre „slabú“ indukciu by predpokladala, že pre nejakú ľubovoľnú hodnotu „n“-znova použime „k“, ktoré tvrdenie platí. Tento predpoklad by sme potom použili na dokázanie, že ďalšia hodnota v reťazci je pravdivá, čo nám umožní dospieť k záveru, že náš návrh je celkovo platný. Avšak pre tento návrh, predpoklad, že P (k) je pravdivý, nám nič nehovorí o P (k + 1). Tento typ „slabého“ predpokladu je tu nedostatočný, takže budeme musieť predpokladať viac. Indukčná hypotéza „silnej“ indukcie namiesto jednoduchého predpokladu, že P (k) je pravdivá, predpokladá, že pre všetky hodnoty „n“medzi základným prípadom a „k“, aby bol návrh pravdivý. Toto použijeme porovnateľne silnejší predpoklad (tj. predpokladáme viac) na dokázanie pravdivosti tvrdenia.
- Tento typ „silného“ predpokladu odlišuje tieto dve formy dôkazov.
- V tomto prípade budeme predpokladať, že pre nejakú hodnotu k ≥ 2 bude každé celé číslo "n" také, že 2 ≤ n ≤ k môže byť zapísané ako súčin prvočísel.
- 5Dokážte, že „silná“ induktívna hypotéza platí pre ďalšiu hodnotu v reťazci. Teraz použijeme tento silný predpoklad na dokázanie, že platí aj P (k + 1), čím celkovo dokážeme platnosť nášho návrhu. Pre „k + 1“ existujú dva relevantné výsledky. Ak je „k + 1“ prvočíslo, náš návrh platí a máme hotovo. Ak „k + 1“ nie je prvočíslo, bude mať najmenší prvočíselný faktor, ktorý označíme ako „p“. Preto „k + 1“ môže byť vyjadrené ako súčin „p“ a nejakého iného čísla „x“. Pretože „x“ bude nevyhnutne menšie ako „k“, hovorí naša induktívna hypotéza us, že „x“ je možné zapísať ako súčin prvočísel, čo v konečnom dôsledku znamená, že bez ohľadu na to, či je „k + 1“ prvočíslo alebo nie, je možné ho zapísať ako súčin prvočísel.
- 6Záver, že tento návrh je platne dokázaný silnou matematickou indukciou. Použitím našej „silnej“ induktívnej hypotézy sme dokázali dokázať, že náš návrh platí, keď by „slabá“ indukcia na to nebola dostatočná. Skúste najskôr „slabú“ indukciu, pretože skutočnosť, že teoreticky predpokladáte menej, posilňuje logiku dôkazu, na rozdiel od konvencií pomenovania použitých pre tieto dva typy dôkazov. Matematicky sú však tieto dve formy indukcie ekvivalentné.
Takto funguje matematická indukcia a nasledujúce kroky budú ilustrovať, ako vytvoriť formálny indukčný dôkaz.
- V „slabom“ indukčnom dôkaze v konečnom dôsledku hľadáte spojenie medzi P (k) a P (k + 1), aby ste dokázali, že váš návrh je pravdivý. V „silnom“ indukčnom dôkaze hľadáte spojenie medzi P (ľubovoľná hodnota „n“ medzi základným prípadom a „k“) a P (k + 1).
- Ak platí „silná“ indukcia, platí aj pravidelná indukcia a naopak. Pamätajte si, že tieto dva typy dôkazov sú ekvivalentné a jeden nie je vo svojej podstate lepší ako druhý. „Silná“ indukcia niekedy ponúka trochu pomoci pri písaní dôkazu, keď induktívna hypotéza pre „slabú“ indukciu jasne nedokazuje predložený návrh.
- Indukcia funguje na základe princípu dobrého poriadku. To znamená, že každá neprázdna množina kladných celých čísel má najmenší prvok. V našom prípade bol tento najmenší prvok 1.
- Indukcia sa bežne používa na dôkaz, že vlastnosť je pravdivá pre všetky prirodzené čísla. To znamená, že budete pracovať s kladnými celými číslami (bez zlomkov alebo s celými číslami).
V „silnom“ indukčnom dôkaze hľadáte spojenie medzi P (ľubovoľná hodnota „n“ medzi základným prípadom a „k“) a P (k + 1).
- Nezabudnite na základné puzdrá! Tento jednoduchý krok je často ľahké prehliadnuť, pretože je dosť triviálny. Váš indukčný dôkaz však bude bez neho neúplný.
- Nenechajte zmiasť matematickú indukciu s konceptom induktívnej uvažovania, v ktorom je jeden pokusy dosiahnuť pravdepodobný záver, založený na pozorované dôkazov. Matematická indukcia je vlastne deduktívne uvažovanie, ktoré pomocou logiky prechádza z určitých jasných premís k definitívnemu záveru.
Prečítajte si tiež: Ako pomenovať svoju fanfikciu?
Komentáre (1)
- Neuveriteľné. Vysvetlené oveľa lepšie ako ktorýkoľvek učiteľ, tútor alebo profesor, akého som kedy mal. Ďakujem tomu, kto to napísal.
