Induktion (matematik)

For alternative betydninger, se Induktion. (Se også artikler, som begynder med Induktion)

Der er for få eller ingen kildehenvisninger i denne artikel, hvilket er et problem. Du kan hjælpe ved at angive troværdige kilder til de påstande, som fremføres i artiklen.

Induktion er en bestemt type matematisk bevis, som er meget velegnet til at bevise at en matematisk hypotese er sand for alle naturlige tal, eller andre , som er velordnet.

Induktionsprincippet består af 2 skridt: basisskridtet (induktionsstarten, startbetingelsen) og induktionsskridtet.

1. Basisskridt: I basisskridtet beviser man at hypotesen er sand ved det mindste tal i talmængden. Dette er typisk 1, da man ofte vil bevise sætningen for de naturlige tal.
2. Induktionsskridt: I induktionsskridtet beviser man, at hvis hypotesen gælder for tallet n (denne antagelse kaldes induktionsantagelsen), så gælder den også for tallet n+1.

På denne måde kan man bevise at hypotesen gælder for alle hele tal fra basisskridtet og opefter. Hvis tilfælde 1 er sand, så er tilfælde 2 også sand, da tilfælde 1 er sand. Så er 3 også sand, når 2 er sand, osv.

Dette princip kan sammelignes med dominoeffekten. Hvis du har en lang række dominobrikker stående efter hinanden, kan du udlede følgende:

1. Basisskridt: Den første dominobrik vælter.
2. Induktionsskridt: Når en dominobrik vælter, vil den næste vælte.

Derfor vil alle dominobrikker vælte.

Eksempel

Vi ønsker at bevise følgende sætning med induktionsmetoden:

${\displaystyle \sum _{i=1}^{n}(2i-1)=n^{2},\qquad n\in \mathbb {N} .}$

Først beviser vi at basisskridtet er sand, dvs. at sætningen er sand ved n=1:

${\displaystyle \sum _{i=1}^{1}(2i-1)=2\cdot 1-1=1=1^{2}.}$

Vi har hermed bevist at sætningen er sand, hvis n er 1. Vi vil nu bevise induktionsskridtet ved at bevise, at hvis sætningen gælder for n, dvs. at hvis

${\displaystyle \sum _{i=1}^{n}(2i-1)=n^{2},}$

så gælder den også for n+1. Vi skal altså vise følgende ligning:

${\displaystyle \sum _{i=1}^{n+1}(2i-1)=(n+1)^{2}.}$

Først skiller vi udtrykket lidt ad:

${\displaystyle \sum _{i=1}^{n+1}(2i-1)=\sum _{i=1}^{n}(2i-1)+(2(n+1)-1).}$

Vi bruger nu vores induktionsantagelse til at regne videre og får, at

${\displaystyle \sum _{i=1}^{n}(2i-1)+(2(n+1)-1)=n^{2}+(2(n+1)-1).}$

Så ganger vi parenteserne ud og reducerer:

${\displaystyle \sum _{i=1}^{n+1}(2i-1)=n^{2}+(2n+2-1)=n^{2}+2n+1=(n+1)^{2}.}$

Vi har hermed bevist induktionsskridtet.

Basisskridtet og induktionsskridtet beviser i fællesskab, at sætningen gælder for alle de naturlige tal.