Induksjon

La P(n) være et åpent utsagn, definert for alle naturlige tall n  N.

For eksempel kan P(n) være:

(1) Summen av de n første oddetallene er lik n2: 1 + 3 + 5 + ... + (2n-1) = n2.

(2) Differansen n3 – n er delelig med 3.

(3) Det n-te Fibonacci-tallet er gitt ved formelen

F(n) =

der  = (1 + sqrt(5))/2 = 1,618... er det gyldne snitt.

Matematisk induksjon er en metode for å bevise utsagnet

n P(n)

dvs. at P(n) er sann for hver n  1.

Metoden består i å vise to ting:

(1) Utgangstilfellet P(1) er sant.

(2) Dersom utsagnet P(k) er sant så er også det neste utsagnet P(k+1) sant, for hver k  1.

2005-03-02T15:06:47