Matematisk induksjon

Matematisk induksjon er et logisk prinsipp i matematikk som kan brukes for å bevise påstander indeksert av naturlige tall. Metoden går ut på først å vise at påstanden gjelder for n=1, for så vise at om påstanden gjelder for et vilkårlig tall, så gjelder den for neste. Induksjonsprinsippet sier da at påstanden gjelder for alle naturlige tall.

Metoden 

Et induksjonsbevis består av flere steg. Anta at det er en påstand P(n) som vi ønsker å vise at gjelder for alle naturlige tall n. Vi går da fram som følger:

 Grunntilfellet: Vi må sjekke at påstanden gjelder for n=1, det vil si at P(1) er sann.
 Induksjonssteget: I dette steget antar vi at vi har vist at påstanden gjelder for n=k, det vil si, vi antar at P(k) er sann. Vi ønsker å vise at dette medfører at P(k+1) er sann. Induksjonsprinsippet sier da at påstanden gjelder for alle naturlige tall. Antakelsen vi gjorde (at P(k) er sann), kalles gjerne induksjonshypotesen.

Ideen bak induksjonsprinsippet kan illustreres med dominobrikker. Anta vi har en lang rekke dominobrikker stilt opp etter hverandre. 
 Dominobrikke nummer én faller.
 Om brikke nummer k faller, faller også nummer k+1.
Vi ser at disse to faktaene medførerer at alle brikkene til slutt vil falle.

Eksempel 
Induksjonsprinsippet kan illustreres med et eksempel. Vi ønsker å bevise følgende påstand:
, der n er et naturlig tall.

Sagt med ord, ønsker vi å vise at summen av de n første heltallene er lik formelen på høyresiden over. Første steg i induksjonsbeviset er å sjekke at påstanden stemmer for n=1. Dette er ikke annet enn å sjekke at summen av de én første tallene er lik . Siden

stemmer dette åpenbart.

Induksjonssteget består i å anta at påstanden stemmer for n=k, og vise at dette medfører at påstanden er sann for n=k+1. Det vil si, vi antar at

Påstanden for n=k+1 sier at

Vi regner:

Som var akkurat det vi ønsket å få. Vi har nå vist at om påstanden er sann for n=k, så er den sann for n=k+1. Ved induksjonsprinsippet er vi ferdige.

Litteratur 
 Lindstrøm, Tom (2006). Kalkulus. Universitetsforlaget. ISBN 9788215009773.

Matematisk logikk