Matematisk induktion

Matematisk induktion er en ofte brugt bevismetode i matematik, oftest når vi arbejder med naturlige tal eller med en anden talfølge.

Princip

Det grundlæggende princip er, at vi beviser den givne påstand for et første element, i de naturlige tal oftest n = 1. Det beviser vi ved simpel indsættelse. I det næste trin, induktionsskridtet, beviser vi implikationen »hvis påstanden gælder for n = a, så gælder den også for n = a + 1«.

Ud fra disse to trin kan vi udlede, at det givne udtryk gælder for alle n (fra en eller anden mængde, vi lige arbejder med). Hvorfor er det sådan? I begyndelsen beviser vi, at udtrykket gælder for n = 1. Samtidig ved vi, at hvis udtrykket gælder for n = a, gælder det også for n = a + 1. Vi vælger derfor a = 1. Vi ved, at udtrykket gælder for a = 1, og vi ved også, at det gælder for a + 1 = 2. På dette tidspunkt ved vi, at udtrykket gælder for a = 2. Men fordi det også gælder for a + 1, må det også gælde for 2 + 1 = 3. Og så videre.

Første eksempel

Det første eksempel bliver trivielt. Vi beviser, at hvis vi lægger to til et hvilket som helst lige tal, får vi igen et lige tal. Fordi vi bevæger os i de naturlige tal, skriver vi et generelt lige tal som 2n, hvor n er et naturligt tal. Hvis vi sætter et hvilket som helst naturligt tal ind for n, får vi som resultat et lige tal, det kan ses ved første øjekast. Delelighed skrives med en lodret streg sådan:

$$2\mid 2n$$

Denne skrivemåde betyder, at to går op i udtrykket 2n. Nu hvor vi kan skrive delelighed, kan vi også skrive det, vi skal bevise ved matematisk induktion.

$$2\mid 2n+2;n\in \mathbb{N}$$

Det skal vi bevise i det første eksempel, altså at to går op i udtrykket 2n + 2 — det svarer præcis til den oprindelige opgave i ord »hvis vi lægger to til et hvilket som helst lige tal, får vi igen et lige tal«.

I det første trin af induktionen beviser vi det for det første element, for tallet et. Vi sætter n = 1 ind i udtrykket:

$$\begin{array}{rcl}2& \mid & 2\cdot 1+2\\ 2& \mid & 4\end{array}$$

To går op i fire, så det gælder for det første element. Derefter kommer induktionsskridtet, hvor vi skal bevise, at hvis det gælder for det a-te element, så gælder det også for det (a + 1)-te element. I begyndelsen antager vi, at vores antagelse gælder, altså n = a:

$$2\mid 2a+2$$

Om dette udtryk antager vi, at det er sandt — vi bruger det, når vi konstruerer beviset. Nu vil vi bevise, at

$$2\mid 2(a+1)+2.$$

Hvad har vi gjort? I stedet for a har vi skrevet (a + 1). Parenteserne er vigtige, dette udtryk ville være forkert: 2a + 1 + 2. Vi lægger ikke en til hele udtrykket, men gør virkelig a til et udtryk, der er én større, altså (a + 1). Udtrykket omformer vi ved at gange parentesen ud.

$$\begin{array}{rcl}2& \mid & 2(a+1)+2\\ 2& \mid & 2a+2+2\end{array}$$

Nu en lille afstikker om delelighed. Hvis vi har to tal, lad os sige p og q, der er delelige med et tal, for eksempel r, så gælder det, at også deres sum er delelig med tallet r. Der gælder således:

$$(r\mid p\wedge r\mid q)\Rightarrow r\mid (p+q)$$

Vi kan sætte for eksempel tallene p = 8, q = 20 og r = 4 ind. Vi ser, at fire går op i både otte og tyve. Og på samme måde går den også op i deres sum 8 + 20 = 28.

Hvordan udnytter vi det i vores eksempel? Vi deler højre side op i tallene p og q sådan:

$$p=2a+2;q=2$$

Tallet q, altså to, er trivielt deleligt med to. Og udtrykket p er også deleligt med to, fordi det fortæller antagelsen os. Udtrykket p svarer præcis til vores antagelse, som vi antager er sand. Og hvis p er deleligt med to, og q samtidig er deleligt med to, så er også deres sum delelig med to.

Endnu en gang om antagelsen. I begyndelsen sagde vi, at vi antager, at

$$2\mid 2a+2.$$

Derfor kunne vi, da vi under konstruktionen af beviset stødte på udtrykket 2a + 2, sige om det, at det er deleligt med to. Netop fordi det er vores antagelse. Det er som regel det sværeste trin i matematisk induktion — at forstå, hvornår og hvorfor man må bruge induktionsantagelsen.

Dermed slutter induktionen, beviset er gennemført, sætningen gælder.

Hvis du ville, kunne du opdele det anderledes og slippe for at bruge antagelsen. p = 2n og q = 2 + 2. Tallet q = 4 er trivielt deleligt med to, og det samme gælder p = 2n, for efter divisionen med to står vi tilbage med tallet n, som er et naturligt, altså helt tal. Igen har vi fået to udtryk, som begge er delelige med to, så også deres sum er delelig med to.

I begge tilfælde har vi dog bevist, at

1. det givne udtryk gælder for n = 1,
2. hvis udtrykket gælder for n, så gælder det også for n + 1.

Herfra kan vi allerede udlede:

• Vi ved, at udtrykket gælder for n = 1.
• Hvis det gælder for n, må det også gælde for n + 1, altså også for 1 + 1, altså udtrykket gælder også for n = 2.
• Hvis det gælder for n, må det også gælde for n + 1, altså også for 2 + 1, altså udtrykket gælder også for n = 3.
• Hvis det gælder for n, må det også gælde for n + 1, altså også for 3 + 1, altså udtrykket gælder også for n = 4.
• Hvis det gælder for n, må det også gælde for n + 1, altså også for 4 + 1, altså udtrykket gælder også for n = 5.
• …

Andet eksempel

Dernæst beviser vi ved matematisk induktion en enkel påstand:

$$2^n\ge 2n;n\in \mathbb{N}.$$

Først det første trin, vi undersøger, om påstanden gælder for n = 1 som det første element i de naturlige tal, hvorfra vi vælger n.

$$\begin{array}{rcl}{2}^1& \ge & 2\cdot 1\\ 2& \ge & 2\end{array}$$

Det gælder trivielt. Nu går vi videre til induktionsskridtet, hvor vi skal undersøge, om det, når det gælder for n = a, også gælder for n = a + 1. Vores antagelse er altså, at

$$2^a\ge 2a$$

gælder, og vi vil bevise:

$$2^{a+1}\ge 2(a+1)$$

Venstre side skriver vi først op ved hjælp af regnereglerne for potenser, og højre side ganger vi bare ud.

$$2\cdot 2^a\ge 2a+2$$

På venstre side bruger vi addition i stedet for multiplikation, højre side lader vi være uændret.

$$2^a+2^a\ge 2a+2$$

Nu udnytter vi antagelsen. Antagelsen er en påstand, som vi går ud fra er sand. I uligheden har vi på begge sider to udtryk, der er lagt sammen. Samtidig ved vi dog, at

$$\begin{array}{rcl}{2}^a& \ge & 2a\\ 2^a& \ge & 2.\end{array}$$

Den første linje fortæller antagelsen os, og den anden påstand er triviel (den mindste værdi af 2^a får vi for a = 1, og den er netop lig med to). Vi ved altså, at begge udtryk på venstre side er større end eller lig med begge udtryk på højre side. Dermed har vi med induktion bevist, at hvis udtrykket gælder for a, så gælder det også for (a + 1), og fordi udtrykket også gælder for en, er det givne udtryk sandt.

Tredje eksempel

Vi prøver at bevise følgende påstand:

$$3\mid n\Rightarrow 3\mid n^2;n\in \mathbb{N}$$

I ord: hvis n er deleligt med tre, så er også n² deleligt med tre. Hvis n ikke er deleligt med tre, så gælder udtrykket trivielt (ud fra definitionen af implikation), så vi beskæftiger os med de tilfælde, hvor n er deleligt med tre. Det giver os en talfølge af naturlige tal a_i=3, 6, 9, 12, 15… Fra nu af bevæger vi os i denne talfølge a_i.

Beviset ved induktion begynder vi med det første trin, altså om det gælder for det første element. Jeg minder om, at vi bevæger os i talfølgen a_i, så vi tager det første element i denne talfølge, altså elementet a₁, som er tre. For tre gælder udtrykket:

$$3\mid 3\Rightarrow 3\mid 3^2$$

Nu går vi videre til induktionsskridtet. Vi ser, at talfølgen a_i kunne skrives som 3n, hvor n er et naturligt tal. Altså det andet element er tre større end det foregående osv. Lad os nu antage, at udtrykket gælder for n, og vi skal sikre, at det også gælder for (n + 3), som er den forskrift, der frembringer det næste element i talfølgen, vi bevæger os i. Først skriver vi antagelsen op:

$$3\mid n\Rightarrow 3\mid n^2$$

og så det, vi vil bevise

$$3\mid (n+3)\Rightarrow 3\mid (n+3{)}^2.$$

Vi opløser parentesen på den anden side ved hjælp af formlen:

$$3\mid (n+3)\Rightarrow 3\mid n^2+6n+9.$$

Og nu er vi næsten fremme. På venstre side har vi et udtryk, som helt sikkert er deleligt med tre, fordi n ifølge antagelsen er deleligt med tre (vi bevæger os kun i tal fra talfølgen a_i), og tre er også deleligt med tre. På højre side har vi først n², som ifølge antagelsen er deleligt med tre. Vi ved nemlig, at n er deleligt med tre, og antagelsen siger, at hvis n er deleligt med tre, så er også n² deleligt med tre:

$$3\mid n\Rightarrow 3\mid n^2$$

Dernæst følger udtrykket 6n, som trivielt er deleligt med tre. Du kan forestille dig det som forkortelse af en brøk:

$$\frac{6n}{3}=2n$$

Variablen n er et naturligt tal, så også produktet 2n bliver et naturligt tal, altså efter divisionen med tre fik vi et naturligt tal, og udtrykket 6n må derfor være deleligt med tre. Og tallet ni til sidst er igen deleligt med tre. Udtrykket gælder for det første element og for induktionsskridtet, det er altså sandt.

Antal parenteser i et udtryk

Det sidste eksempel bliver lidt atypisk. Vi prøver at bevise påstanden, at antallet af parenteser i et simpelt udtryk altid er lige, så du kan se, at matematisk induktion kan bruges i en helt anden sammenhæng end bare de naturlige tal. I begyndelsen må vi definere, hvad et simpelt udtryk er. Et simpelt udtryk er:

• et naturligt tal,
• hvis p er et simpelt udtryk, så er også (p²) et simpelt udtryk,
• hvis p og q er simple udtryk, så er også (p + q) et simpelt udtryk.

Så hvad er et simpelt udtryk: 12, 54, (5 + 6), (12 + 7), (6²), ((5 + 6)²). Og omvendt er disse ikke simple udtryk:

• 1 + 2 → de ydre parenteser mangler,
• (1 + 2 → den højre parentes mangler,
• 13² → de ydre parenteser mangler,
• (1 + 2 + 3) → parenteser mangler, rigtigt skulle skrivemåden være (1 + (2 + 3))

Et simpelt udtryk kan for eksempel opstå sådan. I begyndelsen vælger vi et simpelt udtryk (a + b). Nu sætter vi for a det simple udtryk a = (c + d) ind, så vi får ((c + d) + b), og for b sætter vi tre ind: ((c + d) + 3). For c sætter vi ti ind: ((10 + d) + 3) og til sidst for d sætter vi (5²) ind: ((10 + (5²)) + 3). Det er vigtigt at overholde parenteserne, ellers fungerer det ikke.

Nu beviser vi, at et simpelt udtryk indeholder et lige antal parenteser (blandt de lige tal er også nul).

I det første trin af induktionen vælger vi et første element. I dette tilfælde bliver det første element det mest trivielle simple udtryk, nemlig et hvilket som helst naturligt tal. Vi sætter altså

$$j=n;n\in \mathbb{N}.$$

For udtrykket j gælder, at antallet af parenteser er nul, altså det første element opfylder påstanden. I induktionsskridtet antager vi, at vi har to simple udtryk p og q, og at begge har et lige antal parenteser. Så skal vi bevise, at også de simple udtryk (p + q) og (p²) har et lige antal parenteser.

Først addition. Vi definerer desuden funktionen z(q), der giver antallet af parenteser i udtrykket q. Så gælder det, at udtrykket (p + q) har z(p) + z(q) + 2 parenteser. Det har altså to parenteser mere end summen af parenteserne i udtrykkene p og q. Ifølge antagelsen er både z(p) og z(q) lige, så når vi lægger tre lige tal sammen, får vi igen et lige tal. I dette tilfælde gælder påstanden.

Nu til potensen. Igen gælder antagelsen, at det simple udtryk p indeholder et lige antal parenteser. Udtrykket (p²) indeholder så z(p) + 2 parenteser, altså igen to parenteser mere end udtrykket p. Også i dette tilfælde lægger vi lige tal sammen, så resultatet er lige.

Påstanden gælder for det første element og gælder også i induktionsskridtet, derfor er påstanden sand.