Induksjon brukes i matematikken både om induktive definisjoner og induktive bevis (induksjonsbevis).
I skolematematikken møter man eksempler på induksjonsbevis blant annet i forbindelse med Newtons binomialformel for \((a + b)^n\), og formelen for den deriverte av potensfunksjonen \(y = x^n\).
Generelle former for induksjon spiller en sentral rolle innen formale vitenskaper som matematikk, logikk og algoritmeteori (se algoritme).
Et induksjonsbevis bygger alltid på en forutgående induktiv definisjon, og har bare gyldighet da. For eksempel bygger korrektheten av de induksjonsbevisene som er nevnt ovenfor, på at rekken av de naturlige tall 1, 2, ... n, n + 1, ... er induktivt definert (induktivt karakterisert). De naturlige tall defineres som den minste mengde som inneholder tallet 1, og som er lukket under etterfølgeroperasjonen, som sier at hvis n er med i mengden, så er også n + 1 med. En matematisk formel bevises da induktivt ved først å verifisere den for n = 1, og dernest ved å vise at dersom den er gyldig for n, er den også gyldig for n + 1.
For eksempel kan man vise et fullstendig induksjonsbevis at summasjonsformelen \(1 + 2 + 3 + \dotsc + n = \frac{n(n+1)}{2}\) er riktig for alle naturlige tall \(n\). For n = 1 er formelen riktig, siden det den da sier er:
\[\begin{aligned} 1 &= \frac{1(1+1)}{2} \end{aligned}\]
Vi antar så at formelen er riktig når siste tall er n og viser ut fra dette at formelen også er riktig når det siste tallet er n + 1:
\[\begin{aligned} 1 + 2 + 3 + \dotsc + n + (n+1) &= \frac{n(n+1)}{2} + (n+1) \\& = \frac{n(n+1)}{2} + \frac{2(n+1)}{2}\\& = \frac{n(n+1) + 2(n+1)}{2} \\&= \frac{(n+1)(n+2)}{2}\end{aligned}\]
Formelen er altså gyldig for alle naturlige tall.
En induktiv definisjon består av tre ledd: et basistrinn, et induksjonstrinn og en ekstremalbetingelse.
Basistrinnet angir direkte visse elementer i den søkte mengde. I eksempelet med de naturlige tall er det tallet 1 som angis.
Induksjonstrinnet tillater oss å definere nye elementer i den søkte mengde ut fra allerede gitte elementer i mengden. Ved de naturlige tall er det etterfølgeroperasjonen som gir de nye elementene.
Ekstremalbetingelsen sier at den søkte mengde skal være den minste mengde som inneholder elementene fra basis, og som er lukket under de krav som ligger i induksjonstrinnet.
Et induksjonsbevis med utgangspunkt i en slik definisjon består i å først bevise utsagnet for de gitte «basiselementene», og deretter vise at om utsagnet gjelder for et vilkårlig element i mengden, vil det gjelde for et hvilket som helst element man kan danne ved hjelp av induksjonstrinnet.
Mer generelle induktive definisjoner kan tilbakeføres til induktive definisjoner av mengder. Et viktig eksempel fra logikken karakteriserer induktivt klassen av teoremer innen et formalt system (se bevis) som den minste klasse formler som inneholder aksiomene (basis), og som er lukket under systemets slutningsregler (induksjonstrinnet). Induktive definisjoner og konstruksjoner forekommer også hyppig innen algoritmeteori, der basis svarer til en direkte beregning, og induksjonsleddet svarer til en såkalt beregningsløkke («loop»).
Kommentarer
Kommentarer til artikkelen blir synlig for alle. Ikke skriv inn sensitive opplysninger, for eksempel helseopplysninger. Fagansvarlig eller redaktør svarer når de kan. Det kan ta tid før du får svar.
Du må være logget inn for å kommentere.