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

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 talmængder, 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:

∑i=1n(2i−1)=n2,n∈N.displaystyle sum _i=1^n(2i-1)=n^2,qquad nin mathbb N .

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

∑i=11(2i−1)=2⋅1−1=1=12.displaystyle sum _i=1^1(2i-1)=2cdot 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

∑i=1n(2i−1)=n2,displaystyle sum _i=1^n(2i-1)=n^2,

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

∑i=1n+1(2i−1)=(n+1)2.displaystyle sum _i=1^n+1(2i-1)=(n+1)^2.

Først skiller vi udtrykket lidt ad:

∑i=1n+1(2i−1)=∑i=1n(2i−1)+(2(n+1)−1).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

∑i=1n(2i−1)+(2(n+1)−1)=n2+(2(n+1)−1).displaystyle sum _i=1^n(2i-1)+(2(n+1)-1)=n^2+(2(n+1)-1).

Så ganger vi parenteserne ud og reducerer:

∑i=1n+1(2i−1)=n2+(2n+2−1)=n2+2n+1=(n+1)2.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.