Matematisk induksjon

Matematisk induksjon er en mye brukt bevismetode i matematikk, oftest når vi arbeider med naturlige tall eller en annen følge.

Prinsippet

Det grunnleggende prinsippet er at vi beviser påstanden for et første element, i de naturlige tallene er det oftest n = 1. Det beviser vi ved enkel innsetting. I det neste steget, induksjonssteget, beviser vi implikasjonen «hvis påstanden gjelder for n = a, så gjelder den også for n = a + 1».

Fra disse to stegene kan vi utlede at uttrykket gjelder for alle n (fra en mengde vi arbeider med). Hvorfor er det slik? I begynnelsen beviser vi at uttrykket gjelder for n = 1. Samtidig vet vi at hvis uttrykket gjelder for n = a, gjelder det også for n = a + 1. Vi velger a = 1. Vi vet at uttrykket gjelder for a = 1, og vi vet også at det gjelder for a + 1 = 2. Nå vet vi altså at uttrykket gjelder for a = 2. Men siden det også gjelder for a + 1, må det gjelde for 2 + 1 = 3. Og så videre.

Første eksempel

Det første eksemplet blir trivielt. Vi skal bevise at hvis vi legger til to til et hvilket som helst partall, får vi igjen et partall. Siden vi holder oss til de naturlige tallene, skriver vi et vilkårlig partall som 2n, der n er et naturlig tall. Hvis vi setter inn et hvilket som helst naturlig tall for n, får vi et partall som resultat, det ser vi med en gang. Delelighet skrives med en loddrett strek slik:

$$2\mid 2n$$

Denne skrivemåten betyr at to går opp i uttrykket 2n uten rest. Nå som vi kan skrive delelighet, kan vi også skrive det vi skal bevise med matematisk induksjon.

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

Dette skal vi bevise i det første eksemplet, altså at to går opp i uttrykket 2n + 2. Det svarer nøyaktig til den opprinnelige oppgaveteksten «hvis vi legger til to til et hvilket som helst partall, får vi igjen et partall».

I det første steget av induksjonen beviser vi det for det første elementet, for én. Vi setter n = 1 inn i uttrykket:

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

To går opp i fire uten rest, så det gjelder for det første elementet. Nå kommer induksjonssteget, der vi må bevise at hvis det gjelder for element nummer a, så gjelder det også for element nummer (a + 1). I begynnelsen antar vi at antakelsen vår gjelder, altså n = a:

$$2\mid 2a+2$$

Om dette uttrykket antar vi at det er sant, og vi bruker det når vi konstruerer beviset. Nå vil vi bevise at

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

Hva gjorde vi? I stedet for a skrev vi (a + 1). Parentesene er viktige, dette uttrykket ville vært feil: 2a + 1 + 2. Vi legger ikke til én til hele uttrykket, men gjør faktisk a om til et uttrykk som er én større, altså (a + 1). Uttrykket omformer vi ved å multiplisere ut parentesen.

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

Nå en liten avstikker om delelighet. Hvis vi har to tall, la oss si p og q, som er delelige med et tall, for eksempel r, så er også summen deres delelig med r. Det gjelder altså:

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

Vi kan for eksempel sette inn tallene p = 8, q = 20 og r = 4. Vi ser at fire går opp i både åtte og tjue. Og det går likedan opp i summen deres, 8 + 20 = 28.

Hvordan bruker vi dette i eksemplet vårt? Vi deler høyre side opp i tallene p og q slik:

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

Tallet q, altså to, er trivielt delelig med to. Og uttrykket p er også delelig med to, fordi antakelsen sier det. Uttrykket p svarer nøyaktig til antakelsen vår, som vi antar er sann. Og hvis p er delelig med to og samtidig q er delelig med to, så er også summen deres delelig med to.

Nok en gang om antakelsen. I begynnelsen sa vi at vi antar følgende:

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

Derfor kunne vi, da vi under konstruksjonen av beviset støtte på uttrykket 2a + 2, si at det er delelig med to, nettopp fordi det er antakelsen vår. Dette er vanligvis det vanskeligste steget i matematisk induksjon: å forstå når og hvorfor vi kan bruke induksjonsantakelsen.

Dermed er induksjonen ferdig, beviset er gjennomført, og setningen gjelder.

Hvis du vil, kan du dele det opp annerledes og slippe å bruke antakelsen: p = 2n og q = 2 + 2. Tallet q = 4 er trivielt delelig med to, og det samme er p = 2n, for etter at vi har delt på to, står vi igjen med tallet n, som er naturlig, altså et heltall. Igjen har vi fått to uttrykk som begge er delelige med to, så summen deres er også delelig med to.

I begge tilfellene har vi imidlertid bevist at

1. uttrykket gjelder for n = 1,
2. hvis uttrykket gjelder for n, så gjelder det også for n + 1.

Herfra kan vi utlede:

• Vi vet at uttrykket gjelder for n = 1.
• Hvis det gjelder for n, må det gjelde for n + 1, altså for 1 + 1, altså gjelder uttrykket for n = 2.
• Hvis det gjelder for n, må det gjelde for n + 1, altså for 2 + 1, altså gjelder uttrykket for n = 3.
• Hvis det gjelder for n, må det gjelde for n + 1, altså for 3 + 1, altså gjelder uttrykket for n = 4.
• Hvis det gjelder for n, må det gjelde for n + 1, altså for 4 + 1, altså gjelder uttrykket for n = 5.
• …

Andre eksempel

Videre beviser vi en enkel påstand med matematisk induksjon:

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

Først det første steget: Vi undersøker om påstanden gjelder for n = 1, som er det første elementet i de naturlige tallene, som vi velger n fra.

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

Det gjelder trivielt. Nå går vi til induksjonssteget, der vi må undersøke om det også gjelder for n = a + 1 når det gjelder for n = a. Antakelsen vår er altså at

$$2^a\ge 2a$$

gjelder, og vi vil bevise:

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

Venstre side skriver vi først ut ved hjelp av potensreglene, og høyre side multipliserer vi bare ut.

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

På venstre side bruker vi addisjon i stedet for multiplikasjon, og høyre side lar vi stå uendret.

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

Nå bruker vi antakelsen. Antakelsen er et utsagn som vi antar er sant. I ulikheten har vi på begge sider to uttrykk som er lagt sammen. Samtidig vet vi at

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

Den første linjen sier antakelsen, og det andre utsagnet er trivielt (den laveste verdien av 2^a er for a = 1, og den er lik akkurat to). Vi vet altså at på venstre side er begge uttrykkene større enn eller lik begge uttrykkene på høyre side. Dermed har vi bevist ved induksjon at hvis uttrykket gjelder for a, så gjelder det også for (a + 1), og siden uttrykket også gjelder for én, er uttrykket sant.

Tredje eksempel

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

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

Med ord: Hvis n er delelig med tre, så er også n² delelig med tre. Hvis n ikke er delelig med tre, gjelder uttrykket trivielt (fra definisjonen av implikasjon), så vi tar for oss tilfellene der n er delelig med tre. Det gir oss følgen av naturlige tall a_i=3, 6, 9, 12, 15… Fra nå av holder vi oss til denne følgen a_i.

Vi begynner beviset ved induksjon med det første steget, altså om det gjelder for det første elementet. Jeg minner om at vi holder oss til følgen a_i, så vi tar det første elementet i denne følgen, altså elementet a₁, som er tre. For tre gjelder uttrykket:

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

Nå går vi til induksjonssteget. Vi ser at følgen a_i kan skrives som 3n, der n er et naturlig tall. Det andre elementet er altså tre større enn det forrige, og så videre. Anta nå at uttrykket gjelder for n, og vi må sørge for at det også gjelder for (n + 3), som er regelen som gir det neste elementet i følgen vi holder oss til. Først skriver vi antakelsen:

$$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 multipliserer ut parentesen på den andre siden ved hjelp av formelen:

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

Og nå er vi nesten i mål. På venstre side har vi et uttrykk som helt sikkert er delelig med tre, for n er etter antakelsen delelig med tre (vi holder oss bare til tall fra følgen a_i), og tre er også delelig med tre. På høyre side har vi først n², som etter antakelsen er delelig med tre. Vi vet nemlig at n er delelig med tre, og antakelsen sier at hvis n er delelig med tre, så er også n² delelig med tre:

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

Videre følger uttrykket 6n, som er trivielt delelig med tre. Du kan tenke deg det som forkorting av en brøk:

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

Variabelen n er et naturlig tall, så produktet 2n blir også et naturlig tall, altså fikk vi et naturlig tall etter å ha delt på tre, og uttrykket 6n må dermed være delelig med tre. Og nieren på slutten er igjen delelig med tre. Uttrykket gjelder for det første elementet og for induksjonssteget, og er dermed sant.

Antall parenteser i et uttrykk

Det siste eksemplet blir litt uvanlig. Vi prøver å bevise påstanden at antallet parenteser i et enkelt uttrykk alltid er partall, slik at du ser at matematisk induksjon kan brukes i en helt annen sammenheng enn bare naturlige tall. I begynnelsen må vi definere hva et enkelt uttrykk er. Et enkelt uttrykk er:

• et naturlig tall,
• hvis p er et enkelt uttrykk, så er også (p²) et enkelt uttrykk,
• hvis p og q er enkle uttrykk, så er også (p + q) et enkelt uttrykk.

Enkle uttrykk er altså for eksempel: 12, 54, (5 + 6), (12 + 7), (6²), ((5 + 6)²). Og disse er derimot ikke enkle uttrykk:

• 1 + 2 → de ytre parentesene mangler,
• (1 + 2 → høyre parentes mangler,
• 13² → de ytre parentesene mangler,
• (1 + 2 + 3) → parenteser mangler, riktig skrivemåte ville vært (1 + (2 + 3))

Et enkelt uttrykk kan oppstå for eksempel slik. I begynnelsen velger vi det enkle uttrykket (a + b). Nå setter vi inn det enkle uttrykket a = (c + d) for a, og da får vi ((c + d) + b), og for b setter vi inn tre: ((c + d) + 3). For c setter vi inn ti: ((10 + d) + 3), og til slutt setter vi inn (5²) for d: ((10 + (5²)) + 3). Det er viktig å følge reglene for parenteser, ellers fungerer det ikke.

Nå beviser vi at et enkelt uttrykk inneholder et like antall parenteser (null regnes også som partall).

I det første steget av induksjonen velger vi et første element. I dette tilfellet er det første elementet det mest trivielle enkle uttrykket, som er et vilkårlig naturlig tall. Vi setter altså

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

For uttrykket j er antallet parenteser null, så det første elementet oppfyller påstanden. I induksjonssteget antar vi at vi har to enkle uttrykk p og q og at begge har et like antall parenteser. Da må vi bevise at også de enkle uttrykkene (p + q) og (p²) har et like antall parenteser.

Først addisjonen. Vi definerer også en funksjon z(q) som gir antall parenteser i uttrykket q. Da har uttrykket (p + q) z(p) + z(q) + 2 parenteser. Det har altså to parenteser mer enn summen av parentesene i uttrykkene p og q. Etter antakelsen er både z(p) og z(q) partall, og når vi legger sammen tre partall, får vi igjen et partall. I dette tilfellet gjelder utsagnet.

Nå potensen. Igjen gjelder antakelsen om at det enkle uttrykket p inneholder et like antall parenteser. Uttrykket (p²) inneholder da z(p) + 2 parenteser, altså igjen to parenteser mer enn uttrykket p. Også her legger vi sammen partall, så resultatet er et partall.

Utsagnet gjelder for det første elementet og gjelder også i induksjonssteget, derfor er utsagnet sant.