Induksjonsbevis: slik gjør du det steg for steg

Induksjonsbevis er en metode for å vise at en påstand gjelder for alle heltall fra en bestemt startverdi. Du trenger ikke sjekke uendelig mange tilfeller. I stedet viser du at det første tilfellet stemmer, og at påstanden overføres fra hvert tilfelle til det neste.

Dominobrikkene

Standardbildet er en rekke dominobrikker.

Du vil vise at alle brikkene faller. To ting må være på plass:

1. Den første brikken faller.
2. Hvis en vilkårlig brikke faller, velter den den neste.

Har du vist begge deler, kan du konkludere med at alle brikkene faller. Mangler én av delene, har du ikke vist at hele rekken faller.

Det er hele induksjonsprinsippet.

Strukturen i beviset

La P(n) være en påstand som avhenger av heltallet n, og la n₀ være startverdien. Målet er å vise at P(n) er sann for alle n ≥ n₀.

Basissteget: vis at P(n₀) er sann.

Induksjonssteget: Anta at P(k) er sann for et vilkårlig heltall k ≥ n₀. Antakelsen kalles induksjonshypotesen. Bruk den til å vise at P(k + 1) da også er sann.

Konklusjonen: P(n) gjelder for alle heltall n ≥ n₀.

Du antar ikke at påstanden er sann for alle tall. Du viser at hvis den stemmer for et vilkårlig tall k, må den også stemme for k + 1. Basissteget setter denne kjeden i gang.

Eksempel: summen av de n første positive heltallene

Påstand: For alle heltall n ≥ 1 gjelder:

1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}

Basissteg (n = 1):
Venstre side: 1
Høyre side:

\frac{1 \cdot 2}{2} = 1

Likheten holder.

Induksjonshypotese: Anta at følgende gjelder for et vilkårlig heltall k ≥ 1:

1 + 2 + \cdots + k = \frac{k(k+1)}{2}

Induksjonssteg: Vi skal vise at:

1 + 2 + \cdots + k + (k+1) = \frac{(k+1)(k+2)}{2}

Vi bruker induksjonshypotesen på summen 1 + 2 + … + k:

1 + 2 + \cdots + k + (k+1) = \frac{k(k+1)}{2} + (k+1)

Nå trekker vi ut (k + 1) fra begge leddene og får uttrykket:

= (k+1) \left(\frac{k}{2} + 1\right)

Deretter skriver vi uttrykket i parentesen som én brøk:

= (k+1) \cdot \frac{k+2}{2}

Dette er akkurat høyresiden i formelen for k + 1. Derfor har vi vist at formelen gjelder for k + 1.

Konklusjon: Basissteget og induksjonssteget er vist. Derfor gjelder påstanden for alle heltall n ≥ 1.

Vil du øve på en annen summeformel? Les om geometriske rekker, og prøv å bevise formelen for en endelig sum med induksjon.

Sterk induksjon

Sterk induksjon ligner vanlig induksjon. Forskjellen ligger i induksjonshypotesen.

I vanlig induksjon antar du bare at P(k) er sann.

I sterk induksjon antar du at P(n₀), P(n₀ + 1), …, P(k) alle er sanne, altså alle tidligere steg opp til og med k. Så viser du at P(k + 1) følger.

Du får altså bruke hele historikken, ikke bare forrige steg.

Antallet basissteg avhenger av beviset. Hvis overgangen bygger på de to foregående tilfellene, må du sørge for at de to første tilfellene er vist før du bruker denne overgangen.

Når er sterk induksjon nyttig?

Sterk induksjon er nyttig når beviset for P(k + 1) bruker flere tidligere tilfeller.

Et eksempel er rekursive følger, der hvert nytt ledd beregnes fra tidligere ledd. I følgen aₙ = aₙ₋₁ + aₙ₋₂ brukes de to foregående leddene. Da kan det være praktisk å ha begge tilgjengelige i induksjonshypotesen.

Et annet klassisk eksempel er å bevise at ethvert heltall større enn 1 kan skrives som et produkt av primtall. Splitter du n i to mindre faktorer, må du kunne bruke antakelsen på begge, og ingen av dem er nødvendigvis n − 1.

Er sterk induksjon sterkere?

Navnet er litt misvisende. Sterk induksjon kan ikke bevise flere påstander enn vanlig induksjon. De to prinsippene er logisk ekvivalente, og hvert av dem kan utledes fra det andre.

Forskjellen er praktisk. Sterk induksjon gir en mer fleksibel induksjonshypotese, og passer derfor bedre til visse problemer. Vanlig induksjon er ofte nok når neste steg bare trenger forrige steg.

De vanligste feilene

Å hoppe over basissteget. Induksjonssteget viser bare at sannheten overføres fra ett tilfelle til det neste. Du må også vise at påstanden faktisk stemmer ved startverdien.

Å bruke induksjonshypotesen feil. Hypotesen gjelder for k, og ikke for k + 1. Hele poenget er å komme fra det ene til det andre.

Å glemme basissteg ved sterk induksjon. Trenger du to tidligere ledd, må du verifisere to startverdier.

Å velge ett bestemt tall for k og behandle det som et generelt bevis. k skal være et vilkårlig heltall minst lik startverdien. Argumentet må fungere for ethvert slikt k; det er ikke nok bare å skrive ordet «vilkårlig».

Kort oppsummert

Et induksjonsbevis har et basissteg og et induksjonssteg. Først viser du at påstanden stemmer ved startverdien. Så viser du at hvis den stemmer for et vilkårlig heltall k, stemmer den også for k + 1. Sterk induksjon lar deg bruke alle de tidligere tilfellene i antakelsen. Begge variantene kan bevise de samme påstandene.

Se forklaringen på video

Vil du se temaet forklart? Åpne videoleksjonen «Vanlig induksjon og sterk induksjon» i EnkelEksamen. Du må logge inn, og enkelte leksjoner krever tilgang til faget.

Vil du jobbe videre med faget? Se innholdet i Diskret matematikk ved NTNU, eller finn faget som passer til ditt studiested.

Vil du se flere eksempler? Se leksjonen om induksjonsbevis for summeformler og ulikheter.

TMA4412

Matematikk 2C: Diskret matematikk – NTNU

Prøv gratis

Kjøp faget