Induksjonsbevis
Når vi jobbar med matematiske rekker, har vi ofte ein formel for til dømes summen av dei
I matematikken har vi ein bevistype som høver spesielt godt til å vise at slike formlar er rette, det vi kallar induksjonsbevis. Innan logikken inneber induksjon at at vi trekker ei slutning om noko allmenngyldig ut frå enkelttilfelle. Eit matematisk induksjonsbevis har tre viktige nivå:
Trinn 1: Vi viser at påstanden gjeld for ein bestemd verdi av
, som oftast . Dette trinnet blir ofte kalla induksjonsgrunnlaget. Trinn 2: Vi viser at dersom påstanden gjeld for ein generell verdi
, vil han òg gjelde for . Dette trinnet blir kalla induksjonstrinnet. Konklusjon
Vi skal vise korleis induksjonsbevis blir gjennomførte ved hjelp av eit døme.
Vi skal bevise denne påstanden:
Trinn 1
Vi vil først vise at venstre side er lik høgre side for
Påstanden stemmer altså for
Trinn 2
I dette trinnet gjer vi det vi kallar ei antaking. Vi går ut frå at påstanden vår er sann for
Vi går ut frå at
Dette betyr at vi må undersøke om
Det siste leddet på venstre side (det blå) er ledd nummer
Ved å bruke antakinga vår, kan vi skrive om uttrykket slik:
Vi undersøker om venstre side og høgre side er like:
Vi har no vist at dersom påstanden stemmer for
Konklusjon
No har vi det vi treng for å konkludere med at påstanden vår held for alle
Tenk over
I trinn 2 viste vi at dersom påstanden held for
Ei rekke er gitt ved
Vi skal bruke induksjon til å vise at ledd nummer
Trinn 1
Vi ser at
Trinn 2
Vi går ut frå at
Vi undersøker om
Vi sjekkar om venstre side er lik høgre side:
Vi ser at
Konklusjon
Vi har no bevist ved induksjon at