Matematisk induksjon -
Mathematical induction

fra Wikipedia, den frie encyklopedi

Matematisk induksjon kan uformelt illustreres med henvisning til den sekvensielle effekten av fallende dominoer .

Matematisk induksjon er en matematisk bevissteknikk . Den brukes hovedsakelig for å bevise at en setning P ( n ) holder for hvert naturlig tall n  = 0, 1, 2, 3,. . . ; det vil si at den generelle uttalelsen er en sekvens av uendelig mange tilfeller P (0), P (1), P (2), P (3),. . . . Uformelle metaforer hjelper til med å forklare denne teknikken, for eksempel fallende dominoer eller klatring på en stige:

Matematisk induksjon beviser at vi kan klatre så høyt vi vil på en stige, ved å bevise at vi kan klatre opp på bunnetappen ( grunnlaget ) og at vi fra hvert trinn kan klatre opp til neste ( trinnet ).

-  Betongmatematikk , side 3 marginer.

Et bevis ved induksjon består av to saker. Den første, grunnsaken (eller grunnlaget ), beviser utsagnet for n = 0 uten å anta kunnskap om andre tilfeller. Det andre tilfellet, induksjonstrinnet , viser at hvis setningen gjelder for et gitt tilfelle n = k , den også gjelde for neste sak  n = k + 1. Disse to trinnene fastslår at setningen holder for hvert naturlig tall n . Basen tilfelle ikke nødvendigvis å begynne med n = 0, men ofte med n = 1, og eventuelt sammen med et hvilket som helst fast naturlig tall n = N , å etablere sannheten av setningen for alle naturlige tall n ≥ N .

Metoden kan utvides til å bevise uttalelser om mer generelle velbegrunnede strukturer, for eksempel trær ; denne generaliseringen, kjent som strukturell induksjon , brukes i matematisk logikk og informatikk . Matematisk induksjon i denne utvidede betydningen er nært knyttet til rekursjon . Matematisk induksjon er en slutningsregel som brukes i formelle bevis , og er grunnlaget for de fleste korrekthetsbevisene for dataprogrammer.

Selv om navnet antyder noe annet, bør ikke matematisk induksjon forveksles med induktiv resonnement som brukes i filosofien (se Problem med induksjon ). Den matematiske metoden undersøker uendelig mange tilfeller for å bevise en generell uttalelse, men gjør det med en begrenset kjede av deduktive resonnementer som involverer variabelen n , som kan ta uendelig mange verdier.

Historie

I 370 BC, Platon 's Parmenides kan ha inneholdt et tidlig eksempel på en implisitt induktiv sikker. En motsatt iterert teknikk, som teller ned i stedet for opp, finnes i sorittenes paradoks , der det ble hevdet at hvis 1.000.000 sandkorn dannet en haug, og det å fjerne et korn fra en haug etterlot det en haug, så et enkelt sandkorn (eller til og med ingen korn) danner en haug.

I India vises tidlige implisitte bevis ved matematisk induksjon i Bhaskaras " sykliske metode ", og i al-Fakhri skrevet av al-Karaji rundt 1000 e.Kr., som brukte det på aritmetiske sekvenser for å bevise det binomiske teoremet og egenskapene til Pascals trekant .

Ingen av disse gamle matematikerne uttalte imidlertid eksplisitt induksjonshypotesen. En annen lignende sak (i ​​motsetning til det Vacca har skrevet, som Freudenthal nøye viste) var Francesco Maurolico i hans Arithmeticorum libri duo (1575), som brukte teknikken for å bevise at summen av de første n oddetallene er n 2 .

Den tidligste strenge bruken av induksjon var av Gersonides (1288–1344). Den første eksplisitte formuleringen av induksjonsprinsippet ble gitt av Pascal i hans Traité du triangel arithmétique (1665). En annen franskmann, Fermat , brukte rikelig et relatert prinsipp: indirekte bevis ved uendelig nedstigning .

Induksjonshypotesen ble også ansatt av sveitseren Jakob Bernoulli , og fra da av ble den godt kjent. Den moderne formelle behandlingen av prinsippet kom først på 1800 -tallet, med George Boole , Augustus de Morgan , Charles Sanders Peirce , Giuseppe Peano og Richard Dedekind .

Beskrivelse

. Beviset består av to trinn:

  1. Den innledende eller basale saken : bevis at utsagnet holder for 0 eller 1.
.

Forfattere som foretrekker å definere naturlige tall til å begynne med 0 bruker denne verdien i grunntallet; de som definerer naturlige tall til å begynne med 1 bruker den verdien.

Eksempler

Summen av sammenhengende naturlige tall

Matematisk induksjon kan brukes til å bevise følgende setning P ( n ) for alle naturlige tall n .

Dette angir en generell formel for summen av de naturlige tallene mindre enn eller lik et gitt tall; i virkeligheten en uendelig sekvens av utsagn: , , , etc.