Induktion (matematik) | særlig måde at bevise en matematisk sandhed på

Matematisk induktion er en særlig måde at bevise en matematisk sandhed på. Den kan bruges til at bevise, at noget er sandt for alle de naturlige tal (eller alle positive tal fra et punkt og frem). Ideen er, at hvis:

Noget er sandt for det første tilfælde (grundtilfælde);
Når det samme er sandt i et tilfælde, vil det også være sandt i det næste tilfælde (induktivt tilfælde),

derefter

Det samme gælder for alle tilfælde ved induktion.

I matematikkens omhyggelige sprogbrug foregår et bevis ved induktion ofte på følgende måde:

Angiv, at beviset vil blive ført ved induktion over n {\displaystyle n} . ( n {\displaystyle n} er induktionsvariablen.)
Vis, at udsagnet er sandt, når n {\displaystyle n} er 1.
Antag, at udsagnet er sandt for ethvert naturligt tal n {\displaystyle n} . (Dette kaldes induktionstrinnet.)

Vis derefter, at udsagnet er sandt for det næste tal, n + 1 {\displaystyle n+1} $n+1$ .

Fordi det er sandt for 1, så er det sandt for 1+1 (=2, ved induktionstrinnet), så er det sandt for 2+1 (=3), så er det sandt for 3+1 (=4) og så videre.

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.