Matematisk induksjon

Matematisk induksjon er ein metode nytta for matematiske bevis, vanlegvis for å vise at eit visst uttrykk gjeld for alle naturlege tal. Dette er gjort med å vise at det første uttrykket i ei uendeleg rekkje av uttrykk er sann, og så vise at eit vilkårleg uttrykk i den uendelege rekkja er sann, og til slutt det neste uttrykket i rekkja. 

Denne metoden kan utvidast til å bevise uttrykk som gjeld meir generelle velfunderte strukturar, slik som for tre i mengdelære. Denne generaliseringa vert kalla strukturell induksjon og vert nytta i matematisk logikk og datavitskap. 

 Døme 

Her skal vi vise at summen for alle naturlege tal kan skildrast som: 
, der n er eit naturleg tal.

Første skritt er å vise at uttrykket gjeld for 1.

 då n=1. 
Dermed har vi vist at uttrykket gjeld for n=1.

Neste skritt er å vise at om uttrykket gjeld for n=k, medfører det at uttrykket òg gjeld for .

 Antar: 

Legg til k + 1 på begge sider og får:

Reknar ut høgresida:

Dermed har vi:

og beviset er ferdig. Vi har no vist at uttrykket gjeld for n=1, og at om uttrykket gjeld for k, medfører det at uttrykket òg gjeld for k+1. Induksjonsprinsippet seier dermed at uttrykket gjeld for alle naturlege tal .

Kategori:Matematisk logikk
Kategori:Bevisteori
Kategori:Bevis
Kategori:Induktiv tenking