AlegsaOnline.com

Matematisk induktion – definition, princip, bevismetode og eksempler

Lær matematisk induktion: klar definition, principper, trin-for-trin bevismetode og illustrative eksempler — en praktisk guide til studier og opgaveløsning.

Forfatter: Leandro Alegsa Oprettelsesdato: 17. maj 2021 Seneste opdatering: 4. januar 2026

en.wikipedia.org · CC BY-SA 3.0

Matematisk induktion er en særlig måde at bevise en matematisk påstand for alle de naturlige tal (eller for alle heltal fra et bestemt startpunkt og frem). Idéen er enkel: hvis

påstanden er sand for det første relevante tal (grundtilfældet), og
hvis påstanden er sand for et vilkårligt tal n, så medfører det, at påstanden også er sand for n+1 (induktionstrinet),

så følger det ved induktion, at påstanden gælder for alle følgende tal.

Definition og princip

Formelt bruger man ofte denne struktur i et induktionsbevis:

Angiv induktionsvariablen: Beviset føres ved induktion over n . (Denne n kaldes induktionsvariablen.)
Grundtilfælde: Vis, at udsagnet er sandt for det første tal (typisk n = 1 eller n = 0): fx vis at udsagnet holder, når n = 1 .
Induktionsantagelse (IH): Antag at udsagnet gælder for et vilkårligt naturligt tal n .
Induktionstrin: Under denne antagelse skal du vise, at udsagnet så også gælder for det næste tal n+1 $n+1$ . Dette trin kaldes ofte at føre induktionen videre.

Konklusionen er, at fordi udsagnet gælder for grundtilfældet, gælder det for grundtilfældet + 1, så for +2 osv., og dermed for alle relevante naturlige tal.

Variationer og relaterede principper

Induktion fra et andet startpunkt: I stedet for at starte ved 0 eller 1 kan man starte ved et vilkårligt heltal k. Man viser da grundtilfældet for n = k og derefter at n → n+1 holder for alle n ≥ k.
Stærk induktion (fuld induktion): Her antager man som induktionshypotese, at påstanden er sand for alle tal ≤ n, og bruger dette til at vise den for n+1. Stærk induktion er logisk ækvivalent med almindelig induktion, men kan være mere bekvem i nogle beviser.
Velligningsprincippet (well-ordering): Principperne ovenfor er tæt forbundne med well-ordering-princippet, som siger, at enhver ikke-tom mængde af naturlige tal har et mindste element. Disse synspunkter er ækvivalente i formel betydning.

Typiske fejl og faldgruber

At springe over eller kun halvhjertet vise grundtilfældet. Hvis grundtilfældet fejler, kan induktionen ikke starte.
At forveksle induktionsantagelsen med et bevis: man må kun bruge IH som antagelse, ikke for at «vende rundt» og citere det, man skal bevise uden gyldig afledning.
At antage at det er nok at vise n→n+1 for nogle værdier af n i stedet for for alle relevante n (fx kun for lige n). Induktionen skal dække hele kæden fra grundtilfældet frem.

Eksempler

Eksempel 1 — Sumformel

Påstand: Summen af de første n positive heltal er n(n+1)/2, altså

1 + 2 + ... + n = n(n+1)/2 for alle n ≥ 1.

Bevis ved induktion:

Grundtilfælde: For n = 1 er venstresiden 1, højresiden 1(1+1)/2 = 1. OK.
Induktionsantagelse: Antag for et vilkårligt n ≥ 1 at 1 + 2 + ... + n = n(n+1)/2.
Induktionstrin: Så er 1 + 2 + ... + n + (n+1) = [n(n+1)/2] + (n+1) = (n+1)(n/2 + 1) = (n+1)(n+2)/2, hvilket viser påstanden for n+1.
Da grundtilfældet er sandt og induktionstrinet er vist, gælder formlen for alle n ≥ 1.

Eksempel 2 — En ulighed

Påstand: 2^n ≥ n + 1 for alle n ≥ 1.

Bevis:

Grundtilfælde: For n = 1: 2^1 = 2 ≥ 2 = 1+1.
Induktionsantagelse: Antag 2^n ≥ n+1 for et givet n ≥ 1.
Induktionstrin: Så 2^{n+1} = 2·2^n ≥ 2·(n+1) = 2n+2 ≥ n+2, fordi 2n+2 ≥ n+2 for n ≥ 0. Derfor 2^{n+1} ≥ (n+1)+1, som ønsket.

Eksempel 3 — Divisibilitet

Påstand: For alle n ≥ 1 er 4^n − 1 deleligt med 3.

Bevis:

Grundtilfælde: For n = 1: 4^1 − 1 = 3, som er deleligt med 3.
Induktionsantagelse: Antag 4^n − 1 er deleligt med 3 for et bestemt n.
Induktionstrin: 4^{n+1} − 1 = 4·4^n − 1 = 4(4^n − 1) + 3. Da 4^n − 1 er deleligt med 3, er også 4(4^n − 1) deleligt med 3, og da 3 er deleligt med 3 følger, at summen er delelig med 3. Altså gælder det for n+1.

Hvornår er induktion hensigtsmæssig?

Induktion er særligt nyttig, når påstanden for n+1 kan udtrykkes direkte ved hjælp af påstanden for n, eller når man kan bruge antagelsen om alle tidligere tilfælde (stærk induktion). Typiske anvendelser er summationer, rekursive formler, delelighedsudtryk, uligheder afhængige af n og egenskaber ved diskrete strukturer (grafer, træer, ordninger).

Afsluttende bemærkninger

Matematisk induktion er et fundamentalt og kraftfuldt bevisværktøj. Det bygger på den enkle idé om at opstille en «dominoeffekt»: vis at den første domino falder, og at hvert fald får næste domino til at falde — så falder alle. Forståelsen af korrekt opbygning af grundtilfælde og induktionstrin er afgørende for et gyldigt bevis.

Eksempler på beviser ved induktion

Summen af de første n naturlige tal

Bevis, at for alle naturlige tal n:

1 + 2 + 3 + . . . . + ( n - 1 ) + n = 1 2 n ( n + 1 ) {\displaystyle 1+2+3+....+(n-1)+n={\tfrac {1}{2}}}n(n+1)} $1+2+3+....+(n-1)+n={\tfrac {1}{2}}n(n+1)$

Bevis:

For det første kan udsagnet skrives som:

2 ∑ k = 1 n k = n ( n + 1 ) {\displaystyle 2\sum _{k=1}^{n}k=n(n+1)} $2\sum _{k=1}^{n}k=n(n+1)$ (for alle naturlige tal n)

Ved induktion på n,

Først for n=1:

2 ∑ k = 1 1 1 k = 2 ( 1 ) = 1 ( 1 + 1 ) {\displaystyle 2\sum _{k=1}^{1}k=2(1)=1(1+1)} $2\sum _{k=1}^{1}k=2(1)=1(1+1)$ ,

så det er sandt.

Derefter antages det, at for nogle n=n₀ er udsagnet sandt. Det vil sige, at:

2 ∑ k = 1 n 0 k = n 0 ( n 0 + 1 ) {\displaystyle 2\sum _{k=1}^{n_{0}}}k=n_{0}(n_{0}+1)} $2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1)$

Så for n=n₀ +1:

2 ∑ k = 1 n 0 + 1 k {\displaystyle 2\sum _{k=1}^{{n_{0}}}+1}k} $2\sum _{k=1}^{{n_{0}}+1}k$

kan omskrives som

2 ( ∑ k = 1 n 0 k + ( n 0 + 1 ) ) {\displaystyle 2\left(\sum _{k=1}^{n_{0}}}k+(n_{0}+1)\right)} $2\left(\sum _{k=1}^{n_{0}}k+(n_{0}+1)\right)$

Da 2 ∑ k = 1 n 0 k = n 0 ( n 0 + 1 ) , {\displaystyle 2\sum _{k=1}^{n_{0}}}k=n_{0}(n_{0}+1),} $2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1),$

2 ∑ k = 1 n 0 + 1 k = n 0 ( n 0 + 1 ) + 2 ( n 0 + 1 ) + 2 ( n 0 + 1 ) = ( n 0 + 1 ) ( n 0 + 2 ) {\displaystyle 2\sum _{k=1}^{n_{0}+1}k=n_{0}(n_{0}+1)+2(n_{0}+1)=(n_{0}+1)(n_{0}+2)} $2\sum _{k=1}^{n_{0}+1}k=n_{0}(n_{0}+1)+2(n_{0}+1)=(n_{0}+1)(n_{0}+2)$

Beviset er derfor komplet ved induktion.

Summen af de indvendige vinkler i en polygon

Matematisk induktion angives ofte med startværdien 0 (i stedet for 1). Faktisk fungerer den lige så godt med en række forskellige startværdier. Her er et eksempel, hvor startværdien er 3: "Summen af de indvendige vinkler i en n {\displaystyle n} -sidet polygon er ( n - 2 ) 180 {\displaystyle (n-2)180} $(n-2)180$ grader."

Den oprindelige startværdi er 3, og de indvendige vinkler i en trekant er ( 3 - 2 ) 180 {\displaystyle (3-2)180} $(3-2)180$ grader. Antag, at de indvendige vinkler i en polygon med n {\displaystyle n} - sider er ( n - 2 ) 180 {\displaystyle (n-2)180} $(n-2)180$ grader. Tilføj en trekant, som gør figuren til en n + 1 {\displaystyle n+1} $n+1$ -sidet polygon, og det øger antallet af vinkler med 180 grader ( n - 2 ) 180 + 180 = ( n + 1 - 2 ) 180 {\displaystyle (n-2)180+180=(n+1-2)180} $(n-2)180+180=(n+1-2)180$ grader. Da både grundtilfælde og induktionstilfælde er behandlet, er beviset nu færdigt.

Der er mange matematiske objekter, for hvilke beviser ved hjælp af matematisk induktion fungerer. Den tekniske betegnelse er en velordnet mængde.

Induktiv definition

Den samme idé kan bruges til at definere et sæt objekter og til at bevise udsagn om dette sæt objekter.

Vi kan f.eks. definere n {\displaystyle n} fætter af n grad som følger:

En 1 {\displaystyle 1} $1$ fætter eller kusine i 1. grad er barn af en forælders søskende.
En n + 1 {\displaystyle n+1} $n+1$ fætter af 1. grad er barn af en forælders n {\displaystyle n} fætter af 1. grad.

Der findes et sæt aksiomer for aritmetikken af de naturlige tal, som er baseret på matematisk induktion. Dette kaldes "Peanos aksiomer". De udefinerede symboler er | og =. Aksiomerne er

| er et naturligt tal.
Hvis n {\displaystyle n} er et naturligt tal, så er n | {\displaystyle n|} $n|$ et naturligt tal.
Hvis n | = m | {\displaystyle n|=m|} $n|=m|$ så er n = m {\displaystyle n=m} $n=m$ .

Man kan derefter definere addition og multiplikation osv. ved hjælp af matematisk induktion. For eksempel:

m + | = m | {\displaystyle m+|=m|} $m+|=m|$
m + n | = ( m + n ) | {\displaystyle m+n|=(m+n)|} $m+n|=(m+n)|$

Relaterede sider

Matematisk bevis
Bevis ved modsigelse

Spørgsmål og svar

Spørgsmål: Hvad er matematisk induktion?

A: Matematisk induktion er en særlig måde at bevise en matematisk sandhed på, som kan bruges til at bevise, at noget er sandt for alle naturlige tal eller positive tal fra et bestemt punkt og fremefter.

Spørgsmål: Hvordan foregår beviset ved induktion?

Svar: Beviset ved induktion foregår typisk ved at angive, at beviset vil blive udført over n, vise, at udsagnet er sandt, når n er 1, antage, at udsagnet er sandt for ethvert naturligt tal n, og derefter vise, at det er sandt for det næste tal (n+1).

Spørgsmål: Hvad betyder det at antage noget i et induktivt trin?

Svar: At antage noget i et induktivt trin betyder at acceptere det som værende sandt uden at give beviser eller beviser. Det tjener som udgangspunkt for yderligere undersøgelser.

Spørgsmål: Hvilke slags tal anvendes i matematisk induktion?

Svar: Matematisk induktion anvender typisk naturlige tal eller positive tal fra et vist punkt og fremefter.

Spørgsmål: Hvordan kan man vise, at noget er sandt for det næste tal (n+1)?

Svar: For at vise, at noget er sandt for det næste tal (n+1), skal man først bevise, at det er sandt, når n=1, og derefter bruge sin antagelse fra det induktive trin til at vise, at det også er sandt for n+1.

Forfatter

AlegsaOnline.com - Induktion (matematik) - Leandro Alegsa

Oprettelsesdato: 17. maj 2021
Seneste opdatering: 4. januar 2026

URL: https://da.alegsaonline.com/art/62803