Matematinė indukcija

Nelyginio dydžio sluoksnis sudaro kitą kvadratą

Pradėkite nuo vieno taško. Pridėkite L formos sluoksnį iš trijų taškų, kad susidarytų 2 × 2 dydžio kvadratas, tada pridėkite penkis taškus, kad susidarytų 3 × 3 dydžio kvadratas. Bendras taškų skaičius yra 1, 4 ir 9. Paveikslas leidžia manyti, kad pirmųjų n teigiamų nelyginių skaičių suma lygi n². Kaip galėtume tai įrodyti kiekvienam teigiamam sveikajam skaičiui n, užuot tik patikrinę kvadratus, kuriuos galime nupiešti?

k × k dydžio kvadrate yra k² taškų. Norėdami jį padidinti iki (k + 1) × (k + 1) dydžio kvadrato, pridėkite eilutę iš k + 1 taškų ir stulpelį iš k taškų. Kampinis taškas priklauso tik eilutei, todėl nėra skaičiuojamas du kartus. Naujame sluoksnyje yra 2k + 1 taškų – tai kitas nelyginis skaičius.

Lygybė k² + (2k + 1) = (k + 1)² paaiškina šį augimą bet kuriam teigiamam sveikajam skaičiui k. Ji parodo, kaip teisingas bendras taškų skaičius viename etape lemia teisingą bendrą taškų skaičių kitame. Taip pat reikia, kad pirmasis etapas būtų teisingas. Matematinė indukcija sujungia būtent šiuos du faktus: pradžią ir taisyklę, kuri visada leidžia pereiti į kitą etapą.

Pasikartokite algebrą ir pirmiausia perskaitykite vieną įrodymą

„Simboliai, apibrėžimai ir matematinė kalba“ padeda atskirti indeksą nuo teiginio apie jį. „Kintamieji, reiškiniai ir reikšmių įstatymas“ paaiškina, ką reiškia bet kuris k ir kaip vietoj jo įstatyti k + 1. „Skliaustų atskleidimas, skaidymas dauginamaisiais ir algebrinės tapatybės“ pateikia tapatybę (k + 1)² = k² + 2k + 1. „Pavyzdžiai, paaiškinimai ir kontrpavyzdžiai“ padeda atskirti vieną tinkamą pavyzdį nuo bendro pagrindimo.

Skyriaus parengiamoji medžiaga, prie kurios reikėtų grįžti: Teiginiai, tiesos reikšmės ir loginės jungtys; Kvantoriai ir tikslūs matematiniai teiginiai; Tiesioginis įrodymas ir argumentavimas taikant kontrapoziciją. Šioje pamokoje paaiškinamos reikalingos šių temų idėjos.

Pirmasis skaitymas

Sekite augantį kvadratą, paprastosios indukcijos taisyklę ir pirmąjį išspręstą pavyzdį. Tada išnagrinėkite atvejus, kai nepavyksta pagrįsti indukcijos bazės ar žingsnio. Prie stipriosios indukcijos grįžkite tiksliai nustatę, kokia prielaida leidžiama.

Grįžkite prie įrodymo struktūros

Kai įprasta indukcijos bazė ir žingsnis bus aiškūs, dar kartą peržiūrėkite mažiausio atvejo, kuriuo teiginys negalioja, paaiškinimą ir teiginių junginio lygiavertiškumą.

Šio skyriaus temos „Teiginiai, tiesos reikšmės ir loginės jungtys“, „Kvantoriai ir tikslūs matematiniai teiginiai“ bei „Tiesioginis įrodymas ir kontrapozicijos argumentai“ suteikia papildomą loginį pasirengimą. Jų paskirtis paaiškinama čia: P(k) yra vienas teiginys, „kiekvienam k“ apima nurodytus sveikuosius skaičius, o implikacijos išvada turi būti išvedama iš jos prielaidos. Šios skyriaus temos yra pasirengimo medžiaga, prie kurios galima grįžti, o ne papildomos įrodymo prielaidos.

Skaitydami pirmą kartą, sekite didėjančio kvadrato pavyzdį, įprastosios indukcijos taisyklę ir pirmąjį išsamiai pateiktą įrodymą. Tada išnagrinėkite atvejus, kai trūksta indukcijos bazės arba nepavyksta indukcijos žingsnis. Prie stipriosios indukcijos grįžkite tada, kai galėsite tiksliai nusakyti, ką leidžia indukcijos prielaida. Paaiškinimą, kodėl ši taisyklė veikia ir kodėl abi jos formos yra lygiavertės, galima palikti antrajam skaitymui.

P(n) – vienas atvejis; teorema taikoma visiems n

Teiginiui apie kvadratą apibrėžkime P(n) kaip „1 + 3 + 5 + … + (2n − 1) = n²“. Čia n yra teigiamas sveikasis skaičius, todėl suma turi lygiai n dėmenų. P(1) yra teiginys 1 = 1². P(3) yra teiginys 1 + 3 + 5 = 3². Teorema teigia, kad P(n) yra teisingas kiekvienam sveikajam skaičiui n ≥ 1.

Neįtraukite „kiekvienam n“ į P(n) ir tada nelaikykite visos šios teoremos indukcijos prielaida. Prielaida bus vienas atvejis P(k) arba, taikant stipriąją indukciją, tiksliai nurodytas baigtinis atvejų intervalas. Ji nėra siekiama visuotinė išvada.

Šioje pamokoje ℤ žymi sveikuosius skaičius. Sritis n ∈ ℤ, n ≥ n₀ apibrėžia visus sveikuosius indeksus nuo n₀. Pasirenkame n₀ ≥ 0 ir visada jį aiškiai nurodome, todėl susitarimai, ar simboliu ℕ žymima aibė prasideda nuo 0, ar nuo 1, nesukelia dviprasmybės. Čia indukcija taikoma šiems iš eilės einantiems sveikiesiems indeksams, o ne kiekvienai tarp jų esančiai realiajai reikšmei.

Kai kurie teiginiai pradedami nuo 0, kiti – nuo 1 ar vėlesnio indekso. Pradinis indeksas yra teoremos dalis. Įrodymas, prasidedantis nuo 4, nieko neįrodo apie indeksus nuo 0 iki 3, nebent tie atvejai nagrinėjami atskirai. P(n) esantys reiškiniai taip pat turi būti apibrėžti visoje nurodytoje srityje.

Patikrinkite bazę ir įrodykite bendrąjį indukcijos žingsnį

Norėdami įrodyti P(n) kiekvienam sveikajam skaičiui n ≥ n₀, pirmiausia įrodykite P(n₀). Tai indukcijos bazė: ji pradeda grandinę. Tada pasirinkite bet kurį sveikąjį skaičių k ≥ n₀ ir tarkite, kad P(k) teisingas. Remdamiesi šia indukcijos prielaida ir jau nustatytais faktais, išveskite P(k + 1). Taip įrodoma implikacija P(k) ⇒ P(k + 1) kiekvienam tokiam k.

Remdamiesi matematine indukcija, padarykite išvadą, kad P(n) galioja kiekvienam sveikajam skaičiui n ≥ n₀. Abu reikalavimai svarbūs. Pradžia be bendrojo žingsnio tik patikrina pradinį atvejį. Teisingas žingsnis be teisingo pradinio atvejo gali neturėti nuo ko prasidėti.

Prielaida P(k) taikoma tik įrodant implikaciją. Jūs nedarote prielaidos, kad ji jau teisinga kiekvienam k, ir netariate, kad P(k + 1) teisingas. Įrodžius bazę ir implikaciją, indukcija leidžia teigti P(n₀ + 1), tada P(n₀ + 2) ir kiekvieną vėlesnį atvejį. Kiekvienam pasirinktam baigtiniam tiksliniam indeksui pasiekti reikia tik baigtinio skaičiaus grandžių.

Laiptai, kurių pirmoji pakopa pasiekiama ir kuriems yra taisyklė, kaip pasiekti kiekvieną kitą pakopą, yra naudinga analogija. Ji neįrodo nė vieno iš dviejų matematinių reikalavimų. Suformuluokite ir pagrįskite patį teiginį, indukcijos bazę ir bendrąjį skaičiavimą pereinant prie kito indekso.

Didėjančio kvadrato tapatybė leidžia pateikti išsamų įrodymą

Įrodykite P(n): 1 + 3 + … + (2n − 1) = n² visiems sveikiesiems skaičiams n ≥ 1. Indukcijos bazė, kai n = 1: vienintelis dėmuo yra 1, o 1² = 1. Taigi P(1) yra teisingas.

Indukcijos žingsniui pasirinkite bet kurį sveikąjį skaičių k ≥ 1 ir tarkite, kad 1 + 3 + … + (2k − 1) = k². Pirmuosius k + 1 nelyginių dėmenų sudaro šie pirmieji k dėmenų ir naujas dėmuo 2(k + 1) − 1 = 2k + 1.

Pritaikykite indukcijos prielaidą, tada išskleiskite kvadratą: 1 + 3 + … + (2k − 1) + (2k + 1) = k² + 2k + 1 = (k + 1)². Tai yra būtent P(k + 1). Ankstesnė suma pakeista k² remiantis P(k), o ne todėl, kad būtume tarę, jog teorema galioja kiekvienam indeksui.

Patikrinta indukcijos bazė ir žingsnis į kitą narį, atliktas su bet kuriuo indeksu, įrodo tapatybę kiekvienam sveikajam skaičiui n ≥ 1. Brėžinyje parodytas tas pats pridedamas sluoksnis, nieko neskaičiuojant du kartus. Tai baigtinė bendro algebrinio samprotavimo iliustracija, o ne priežastis apriboti teoremos galiojimą pavaizduotais dydžiais.

Pirmasis klaidingas atvejis prieštarautų patikrintam žingsniui

Kitas paaiškinimas remiasi mažiausio elemento savybe: kiekviena netuščia neneigiamų sveikųjų skaičių aibė turi mažiausią elementą. Tarkime, kad indukcijos bazė ir žingsnis į kitą narį yra įrodyti, tačiau teiginys klaidingas ties kuriuo nors leistinu indeksu. Indeksų, ties kuriais teiginys klaidingas, neneigiami poslinkiai n − n₀ turėtų mažiausią reikšmę, taigi būtų pirmasis indeksas m, ties kuriuo teiginys klaidingas.

Indukcijos bazė teisinga, todėl m > n₀. Kadangi m yra pirmasis indeksas, ties kuriuo teiginys klaidingas, P(m − 1) yra teisingas. Patikrintas žingsnis, kai k = m − 1, kuris vis dar yra ne mažesnis už n₀, tuomet leidžia gauti P(m). Tai prieštarauja prielaidai, kad teiginys klaidingas. Todėl teiginys nėra klaidingas ties jokiu leistinu indeksu.

Taip indukcijos taisyklė paaiškinama remiantis mažiausiojo elemento savybe; tai nepanaikina būtinybės įrodyti konkrečios teoremos indukcijos bazę ir žingsnį. Įrodymo prieštaros būdu išmanymas papildomai parengia suprasti šį paaiškinimą. Tačiau pirmiau pateiktą įrodymą įprastosios indukcijos būdu galima suprasti ir prieš tai neišmokus šio atskiro įrodymo metodo.

Vėlesnė bazė užtikrina nelygybės indukcijos žingsnio teisingumą

Nagrinėkime P(n): 2^n ≥ n² sveikiesiems skaičiams n ≥ 4. Kai n = 4, abi pusės lygios 16, taigi baziniu atveju galioja lygybė. Kai n = 3, 8 < 9; teorema, kurios sritis prasidėtų nuo 3, būtų klaidinga.

Tegu k ≥ 4 yra bet kuris sveikasis skaičius ir tarkime, kad 2^k ≥ k². Padauginus iš teigiamo skaičiaus 2, nelygybės kryptis nesikeičia: 2^(k + 1) = 2 × 2^k ≥ 2k². Norėdami gauti reikiamą apatinę ribą (k + 1)², įrodykime, kad 2k² ≥ (k + 1)².

Šių reiškinių skirtumas yra 2k² − (k + 1)² = k² − 2k − 1 = k(k − 2) − 1. Kai k ≥ 4, turime k ≥ 4 ir k − 2 ≥ 2, todėl iš neneigiamų daugiklių apatinių ribų gauname k(k − 2) − 1 ≥ 4 × 2 − 1 = 7 > 0. Vadinasi, 2^(k + 1) ≥ (k + 1)².

Indukcija įrodo teiginį su negriežtąja nelygybe visiems sveikiesiems skaičiams n ≥ 4. Tai nereiškia, kad jis klaidingas kiekvienam ankstesniam indeksui: n = 0, 1 ir 2 taip pat jį tenkina, o 3 – ne. Teisingai nurodyta sritis ir tinkama apatinė riba nereiškia, kad teiginys teisingas tik toje srityje.

Stiprioji indukcija leidžia remtis visu ankstesniu intervalu

Kartais kitam atvejui įrodyti reikia ankstesnio atvejo, kuris nėra tiesiogiai prieš jį einantis atvejis. Taikydami stipriąją indukciją, imkite bet kurį sveikąjį skaičių k ≥ n₀ ir tarkite, kad P(j) galioja kiekvienam sveikajam skaičiui j, tenkinančiam n₀ ≤ j ≤ k. Išveskite P(k + 1). Kartu su P(n₀) tai įrodo visus P(n), kai n yra sveikasis skaičius ir n ≥ n₀.

Indukcijos prielaida apima visą ankstesnį intervalą, įskaitant jo galus. Ji neapima P(k + 1) ir neleidžia naudoti indekso, mažesnio už n₀. Pavyzdžiui, prieš naudodami P(k − 2), patikrinkite, ar n₀ ≤ k − 2 ≤ k.

Žingsnį gali būti įmanoma taikyti tik įrodžius kelis pradinius atvejus. Jei atskirai įrodote P(n₀), …, P(b) ir stipriosios indukcijos sąlyginį teiginį kiekvienam sveikajam skaičiui k ≥ b, pradinių atvejų blokas kartu su šiuo žingsniu apima visus n ≥ n₀. Neįrodykite vien P(n₀), jei pirmasis atvejis, kuriuo teisėtai galite remtis, yra vėlesnis.

Įprastosios indukcijos žingsnyje daroma tik prielaida P(k). Stiprioji indukcija leidžia prielaidomis laikyti daugiau ankstesnių atvejų, todėl įrodymą gali būti lengviau užrašyti. Abi formos leidžia įrodyti tą pačią indeksuotų teoremų klasę; žodis „stiprioji“ apibūdina žingsnyje leidžiamą prielaidą, o ne didesnę loginę galią.

Trys pradinės sumos leidžia pasiekti kiekvieną vėlesnę tikslinę sumą

Įrodykite, kad kiekvieną sveikąjį skaičių n ≥ 12 galima užrašyti n = 3a + 5b, kur a ir b yra neneigiami sveikieji skaičiai. Įsivaizduokite žetonus, kurių vertė yra 3 ir 5 vienetų. Vienetai čia reiškia abstrakčius kiekius, o žetonų skaičius negali būti neigiamas ar trupmeninis. Riba 12 yra pakankama; neteigiame, kad tai mažiausia galima pradinė riba.

Įrodykite tris pradinius atvejus: 12 = 3 × 4 + 5 × 0, 13 = 3 × 1 + 5 × 2 ir 14 = 3 × 3 + 5 × 1. Visi žetonų skaičiai yra neneigiami sveikieji skaičiai.

Stipriosios indukcijos žingsniui pasirinkite bet kurį sveikąjį skaičių k ≥ 14 ir tarkite, kad kiekvieną sveikąjį skaičių j nuo 12 iki k galima taip užrašyti. Toliau reikia įrodyti atvejį k + 1. Už jį mažesnis skaičius k − 2 = (k + 1) − 3 tenkina 12 ≤ k − 2 ≤ k. Todėl pagal indukcijos prielaidą k − 2 = 3a + 5b su tam tikrais neneigiamais sveikaisiais skaičiais a ir b.

Pridėkite vieną 3 vienetų vertės žetoną: k + 1 = (k − 2) + 3 = 3(a + 1) + 5b. Nauji žetonų skaičiai a + 1 ir b tebėra neneigiami sveikieji skaičiai. Taip įrodomas kitas atvejis, todėl pradinių atvejų blokas ir stiprioji indukcija apima kiekvieną sveikąjį skaičių n ≥ 12.

Brėžinyje bendros vertės išdėstytos trimis stulpeliais pagal jų liekaną dalijant iš 3. Rodyklės reiškia 3 pridėjimą, o ne perėjimą prie kito skaitinio indekso. Baziniai atvejai 12, 13 ir 14 pradeda visus tris stulpelius. Stipriosios indukcijos įrodyme galima remtis visomis mažesnėmis leistinomis bendromis vertėmis, todėl pasirinktu mažesniu skaičiumi galima pagrįstai remtis nepriklausomai nuo to, kuriame stulpelyje jis yra.

Jungtinis teiginys leidžia stipriąją indukciją pakeisti paprastąja

Stipriosios indukcijos prielaida apima P(k), todėl stipriosios indukcijos įrodyme galima naudoti bet kurį paprastosios indukcijos perėjimo prie kito atvejo įrodymą. Norėdami pamatyti atvirkštinę kryptį, sujunkite ankstesnius atvejus į Q(k): „P(j) galioja kiekvienam sveikajam skaičiui j, kuriam n₀ ≤ j ≤ k“.

Tarkime, kad stipriosios indukcijos bazinis atvejis ir implikacija yra įrodyti. Q(n₀) yra tas pats teiginys kaip P(n₀), todėl jis teisingas. Pasirinkime bet kurį sveikąjį skaičių k ≥ n₀ ir tarkime, kad Q(k) galioja. Stipriosios indukcijos implikacija duoda P(k + 1), o Q(k) apima visus ankstesnius P(j). Juos sujungę gauname Q(k + 1). Taigi paprastoji indukcija, taikoma Q, įrodo kiekvieną Q(k), vadinasi, ir kiekvieną P(k).

Jei pradinių atvejų blokas apima atvejus iki b imtinai, šį įrodymą su jungtiniu teiginiu pradėkite nuo Q(b), kuris gaunamas iš patikrinto bloko. Įrodymo išvada apima ir ankstesnį bloką, ir kiekvieną vėlesnį atvejį. Taigi net ir esant keliems pradiniams atvejams bei priklausomybei nuo ankstesnių atvejų, naudojama tiksliai apibrėžta pradžia ir žingsnis, apimantis kiekvieną naują įrodomą atvejį.

Trys skirtingos klaidos gali sugriauti indukcijos įrodymą

Trūksta bazinio atvejo: tegul P(n) reiškia n² ≥ 5, kai n yra sveikasis skaičius ir n ≥ 2. Kai k ≥ 2, implikacija P(k) ⇒ P(k + 1) yra teisinga, nes (k + 1)² ≥ k². Tačiau P(2) yra klaidingas: 4 < 5. Teisinga implikacija su klaidinga prielaida nepadaro pirmojo atvejo teisingo. Pradėjus nuo 3, ši teorema būtų pataisyta, tačiau pasikeistų jos nurodyta galiojimo sritis.

Žingsnis negalioja: tegul P(n) reiškia (n − 1)(n − 2)(n − 3)(n − 4) = 0, kai n yra sveikasis skaičius ir n ≥ 1. Pirmieji keturi atvejai yra teisingi, bet P(5) yra klaidingas, nes sandauga lygi 24. Implikacija P(4) ⇒ P(5) yra klaidinga. Keturi sėkmingi patikrinimai neįrodo perėjimo nuo bet kurio atvejo prie kito.

Aprėpties spraga: teiginio P(n), reiškiančio „n yra lyginis“, bazinis atvejis, kai n = 0, yra teisingas, o žingsnis nuo n prie n + 2 yra pagrįstas. Šios jungtys pasiekia tik lyginius neneigiamus sveikuosius skaičius. Jos neįrodo P(n) kiekvienam n ≥ 0; n = 1 yra kontrpavyzdys. Šuolis per 2 nėra įprastas žingsnis prie kito skaičiaus, padidinant n dydžiu 1.

Šuolis per 2 gali aprėpti visus neneigiamus sveikuosius skaičius, jei abiejų liekanų klasių pradiniai atvejai yra teisingi, o jungtys – pagrįstos. Pavyzdžiui, n² ≥ 0 yra teisinga, kai n = 0 ir n = 1, o žingsnis n → n + 2 išsaugo šios nelygybės teisingumą. Tuomet dvi persipinančios grandinės aprėpia visus n ≥ 0. Praktikoje šiai paprastai teoremai indukcijos nereikia; diagrama naudinga norint atskirti aprėptį nuo teisingumo.

Patikrinkite įrodymą baigtiniu modeliu, tada užrašykite bendrą argumentą

Baigtinėje lentelėje pateikiamos tikslios teisingumo reikšmės tik tiems indeksams, kurie joje išvardyti. Vienas klaidingas leistinas atvejis paneigia visuotinį teiginį. Keli teisingi atvejai negali pagrįsti visų be galo daug atvejų ar patvirtinti implikacijos kiekvienam k. Šių diagramų pasiekiamumo žymos susijusios tik su pavaizduotais baziniais atvejais ir jungtimis.

Dalyje „Augantys kvadratai“ numatykite, kiek taškų prideda nauja eilutė ir stulpelis, tada palyginkite jų skaičių su 2k + 1. Dalyje „Bazė, žingsnis ir aprėptis“ atskirkite tikrąją teisingumo reikšmę T arba F nuo to, ar pavaizduota įrodymo grandinė pasiekia tą mazgą. Implikacija su klaidinga prielaida gali būti teisinga, nors jos rodyklė neperduoda jokio įrodyto atvejo.

Dalyje „Ankstesnės sumos“ pasirinkite tikslinį skaičių ir raskite už jį trimis mažesnį ankstesnį skaičių. Prieš atskleisdami tikslią išraišką, patikrinkite abu ankstesnio intervalo galus, ar žetonų skaičiai neneigiami, ir tris pradinius bazinius atvejus. Apskaičiuoti liudytojai iliustruoja konstrukciją; stipriosios indukcijos įrodymas su laisvai pasirinktu indeksu aprėpia kiekvieną vėlesnį sveikąjį skaičių.

Išsamiame rašytiniame indukcijos įrodyme suformuluojama teorema ir jos taikymo sritis, patikrinamas kiekvienas būtinas pradinis atvejis, įvardijamas laisvai pasirinktas leistinas indukcijos žingsnio indeksas, tiksliai užrašoma leidžiama indukcijos prielaida ir pagrįstai išvedamas kitas atvejis. Baigiamajame sakinyje remiantis indukcija aprėpiama visa nurodyta sritis, o ne vien paskelbiama, kad skaitinis dėsningumas tęsiasi.

Išnagrinėti pavyzdžiai

Pabandykite patys

1. Tegu P(n) reiškia 1 + 3 + … + (2n − 1) = n², kai n yra sveikasis skaičius ir n ≥ 1. Užrašykite P(4), indukcijos prielaidą skaičiui k ir teiginį, kurį reikia įrodyti skaičiui k + 1.

   Rodyti atsakymą ir paaiškinimą

   P(4): 1 + 3 + 5 + 7 = 16. Prielaida: pirmųjų k nelyginių dėmenų suma lygi k². Reikia įrodyti: pirmųjų k + 1 nelyginių dėmenų suma lygi (k + 1)².

   P(k) yra viena lygybė bet kuriam teigiamam sveikajam skaičiui k. Tai nėra teiginys, kad visi P(n) jau įrodyti. Naujas dėmuo lygybėje, kurią reikia įrodyti, yra 2k + 1.

2. Įrodykite, kad 1 + 2 + … + n = n(n + 1)/2 visiems sveikiesiems skaičiams n ≥ 1.

   Rodyti atsakymą ir paaiškinimą

   Bazinis atvejis 1: 1 = 1 × 2/2. Tarkime, kad dėmenų iki k imtinai suma lygi k(k + 1)/2. Pridėję k + 1, gauname (k + 1)(k + 2)/2. Taigi pagal matematinės indukcijos principą formulė galioja visiems n ≥ 1.

   Pasirinkime bet kurį sveikąjį skaičių k ≥ 1. Kita suma yra k(k + 1)/2 + (k + 1) = (k + 1)(k/2 + 1) = (k + 1)(k + 2)/2. Pastovus vardiklis 2 nelygus nuliui; išskaidant dauginamaisiais iš prielaidos gaunama reikiama formulė kitam skaičiui.

3. Įrodoma implikacija P(k) ⇒ P(k + 1), kai P(n): n² ≥ 5, o n yra sveikasis skaičius ir n ≥ 2, tada daroma išvada, kad galioja visi P(n). Ko trūksta ir kaip galima pataisyti apibrėžimo sritį?

   Rodyti atsakymą ir paaiškinimą

   P(2) yra klaidingas, nes 4 < 5, todėl grandinė neturi patikrintos pradžios. Pakeitus teoremos sąlygą į n ≥ 3, gaunamas teisingas bazinis atvejis 9 ≥ 5 ir galiojantis indukcijos žingsnis.

   Kai k ≥ 2, (k + 1)² − k² = 2k + 1 > 0, todėl iš teisingo P(k) sektų P(k + 1). Ši implikacija nereiškia, kad P(2) yra teisingas. Pataisius apatinę ribą, pakeičiamas pradinis visuotinis teiginys.

4. Sandauga (n − 1)(n − 2)(n − 3)(n − 4) lygi nuliui, kai n = 1, 2, 3, 4. Kuris pirmasis perėjimas prie kito sveikojo skaičiaus paneigia teiginį, kad ši sandauga lygi nuliui visiems sveikiesiems skaičiams n ≥ 1?

   Rodyti atsakymą ir paaiškinimą

   Perėjimas 4 → 5 negalioja: P(4) yra teisingas, bet P(5) yra klaidingas, nes 4 × 3 × 2 × 1 = 24.

   Ankstesnės tikrintos reikšmės tenkina teiginį, nes vienas dauginamasis lygus nuliui. Kai n = 5, visi dauginamieji nelygūs nuliui. Vienas klaidingas atvejis iš leistinos srities paneigia visuotinę teoremą ir parodo, kad indukcijos žingsnio implikacija yra klaidinga.

5. Teoremai apie visus sveikuosius skaičius n ≥ 0 turime tik teisingą bazinį atvejį P(0) ir žingsnį P(k) ⇒ P(k + 2) kiekvienam k ≥ 0. Kurie indeksai pasiekiami ir kokio papildomo pradinio atvejo reikėtų, kad būtų aprėpta visa sritis?

   Rodyti atsakymą ir paaiškinimą

   Pasiekiami tik 0, 2, 4, … . Atskirai įrodytas P(1), taikant tą patį galiojantį žingsnį, pradeda seką 1, 3, 5, … ir leidžia aprėpti visą sritį.

   2 dydžio šuolis išlaiko lyginumą, todėl iš vieno bazinio atvejo neįmanoma pasiekti abiejų liekanų klasių. Tai visos srities aprėpties reikalavimas; papildomas bazinis atvejis iš tiesų turi būti teisingas. Jei P(n) reiškia, kad n yra lyginis, P(1) yra klaidingas, ir visai sričiai skirtos teoremos neįmanoma pataisyti vien pavadinus šį atvejį baziniu.

6. Įrodyme su 3 ir 5 vienetų vertės žetonais ir baziniais atvejais 12, 13, 14 nagrinėkite tikslinę reikšmę 23. Nurodykite k, naudojamą ankstesnį indeksą, leistiną indukcijos prielaidos intervalą ir tikslų išreiškimą.

   Rodyti atsakymą ir paaiškinimą

   k = 22; ankstesnis indeksas 20 priklauso intervalui 12 ≤ j ≤ 22. Kadangi 20 = 3 × 5 + 5 × 1, pridėję vieną 3 gauname 23 = 3 × 6 + 5 × 1.

   Stipriosios indukcijos prielaida apima kiekvieną sveikąjį skaičių iki k imtinai, o ne vien k. Ankstesnis indeksas yra tikslinė reikšmė − 3 = k − 2; jis yra ne mažesnis nei 12, kai tikslinė reikšmė yra ne mažesnė nei 15. Abiejų rūšių žetonų skaičiai išlieka neneigiami sveikieji skaičiai.

7. Sustiprinkite teoremą apie žetonus, kad ji galiotų visiems sveikiesiems skaičiams n ≥ 8. Pateikite pakankamą pradinių atvejų bloką ir stipriosios indukcijos žingsnį; patikrinkite, ar naudojamas ankstesnis indeksas yra leistinas.

   Rodyti atsakymą ir paaiškinimą

   Baziniai atvejai: 8 = 3 + 5, 9 = 3 × 3, 10 = 5 × 2. Kai k ≥ 10, tikslinei reikšmei k + 1 naudojamas indeksas k − 2 ≥ 8; prie jo išreiškimo pridėkite vieną 3 vienetų žetoną.

   Trys baziniai atvejai apima liekanų klases, atitinkančias 3 pridėjimo žingsnį. Imkime bet kurį k ≥ 10 ir tarkime, kad visi skaičiai nuo 8 iki k turi reikiamą išraišką. Tada 8 ≤ k − 2 ≤ k, todėl žingsnyje galima taikyti indukcijos prielaidą. Indukcija įrodo, kad reikiamą išraišką turi kiekvienas n ≥ 8. Be to, 7 gauti neįmanoma: nenaudojant nė vieno 5 vertės žetono, lieka 7, o tai nėra 3 kartotinis; naudojant vieną, lieka 2; dviejų vertė jau viršija 7. Taigi 8 yra mažiausia pradinė riba teoremai, apimančiai visus nuo jos einančius neneigiamus sveikuosius skaičius.

8. Ar įrodant teoremą sveikiesiems skaičiams n ≥ n₀ stipriosios indukcijos žingsnyje galima daryti prielaidą P(k + 1)? Paaiškinkite, kaip leistinas prielaidas galima sujungti į vieną teiginį, kad būtų galima taikyti paprastąją indukciją.

   Rodyti atsakymą ir paaiškinimą

   Ne. Galima daryti tik prielaidas P(j), kai n₀ ≤ j ≤ k. Sujunkite šiuos atvejus į teiginį Q(k); stipriosios indukcijos žingsnis įrodo naują atvejį P(k + 1), todėl iš Q(k) išplaukia Q(k + 1).

   Jungtinis teiginys išlaiko anksčiau įrodytus atvejus ir prideda lygiai vieną naują atvejį. Jo bazinis atvejis Q(n₀) yra P(n₀). Paprastoji indukcija tuomet įrodo kiekvieną jungtinį teiginį, taigi ir kiekvieną P(n). Taip įrodomas lygiavertiškumas, nedarant prielaidos, kad žingsnio išvada teisinga.

Ką verta įsidėmėti

• Prieš įrodydami suformuluokite nuo indekso priklausantį teiginį ir tiksliai nurodykite nuoseklių sveikųjų skaičių sritį.
• Paprastajai indukcijai reikia teisingo bazinio atvejo ir P(k) ⇒ P(k + 1) kiekvienam leistinam žingsnio indeksui.
• Stiprioji indukcija leidžia remtis visu nurodytu ankstesnių atvejų intervalu; kiekvienas atvejis, kuriuo remiamasi, turi priklausyti šiam intervalui.
• Kelių bazinių atvejų reikia, kai dėl vėliau pradedamo taikyti žingsnio ar šuolio dalis atvejų kitaip liktų neaprėpta.
• Baigtinio skaičiaus atvejų patikra gali atskleisti kontrpavyzdį, tačiau bendras bazinio atvejo ir indukcijos žingsnio argumentas įrodo visus vėlesnius atvejus.
• Paprastosios ir stipriosios indukcijos loginė galia yra lygiavertė; rinkitės tą formą, kuri aiškiai parodo, nuo kurių atvejų priklauso įrodymas.