Induksjonsbevis
Når vi jobber med matematiske rekker, har vi ofte en formel for for eksempel summen av de første leddene i rekka eller en eksplisitt formel for
Induksjonsbevis
I matematikken har vi en bevistype som er spesielt velegnet til å vise at slike formler er riktige, det vi kaller induksjonsbevis. Innen logikken innebærer induksjon at at vi trekker en slutning om noe allmenngyldig ut fra enkelttilfeller. Et matematisk induksjonsbevis har tre viktige nivåer:
Trinn 1: Vi viser at påstanden gjelder for en bestemt verdi av
, som oftestn . Dette trinnet kalles ofte induksjonsgrunnlaget.n = 1 Trinn 2: Vi viser at dersom påstanden gjelder for en generell verdi
, vil den også gjelde fork . Dette trinnet kalles induksjonstrinnet.k + 1 Konklusjon
Vi skal vise hvordan induksjonsbevis gjennomføres ved hjelp av et eksempel.
Vi skal bevise følgende påstand:
Trinn 1
Vi vil først vise at venstre side er lik høyre side for
Påstanden stemmer altså for
Trinn 2
I dette trinnet gjør vi det vi kaller en antakelse. Vi antar at påstanden vår er sann for
Vi antar
Dette betyr at vi må undersøke om
Det siste leddet på venstre side (det blå) er ledd nummer
Ved å bruke antakelsen vår, kan vi skrive om uttrykket slik:
Vi undersøker om venstre side og høyre side er like:
Vi har nå vist at dersom påstanden stemmer for
Konklusjon
Vi har nå det vi trenger for å konkludere med at påstanden vår holder for alle
Tenk over
I trinn 2 viste vi at dersom påstanden holder for
Forklaring
Vi må huske på at i trinn 2 gjorde vi en antakelse om at påstanden holdt for en generell
Vi kan tenke oss matematisk induksjon som et dominospill. Det at alle brikkene faller, innebærer at påstanden er sann. I trinn 2 viser vi at brikkene står nært nok hverandre, slik at en brikke vil rive ned den neste hvis den faller. Men det hjelper ikke at brikkene står nært nok hvis ikke en eneste brikke faller. I trinn 1 viser vi nettopp dette: Brikke nummer 1 faller, og da faller også alle de andre brikkene etter tur.
Eksempel
Ei rekke er gitt ved
Vi skal bruke induksjon til å vise at ledd nummer
Trinn 1
Vi ser at
Trinn 2
Vi antar at
Vi undersøker om
Vi sjekker om venstre side er lik høyre side:
Vi ser at
Konklusjon
Vi har nå bevist ved induksjon at