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.

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:

1. Grunntilfellet: Vi må sjekke at påstanden gjelder for n=1, det vil si at P(1) er sann.
2. 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.

1. Dominobrikke nummer én faller.
2. 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.

Induksjonsprinsippet kan illustreres med et eksempel. Vi ønsker å bevise følgende påstand:

${\displaystyle 1+2+3+\cdots +n={\frac {n(n+1)}{2}}}$, 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 ${\displaystyle {\frac {1\cdot (1+1)}{2}}}$. Siden

${\displaystyle 1={\frac {1\cdot (1+1)}{2}}}$

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

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

Påstanden for n=k+1 sier at

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

Vi regner:

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

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.

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