induktionsbevis

Et induktionsbevis er en matematisk bevismetode, der anvendes til at bevise, at et udsagn \(P(n)\) er sandt for alle naturlige tal (\(n = 1,2,3,...\)).

Beviset forløber i to dele: 1) Vis, at \(P(1)\) er sandt. 2) Antag, at \(P(n)\) er sandt; vis under denne antagelse, at \(P(n+1)\) er sandt. Ved hjælp af 1) og 2) kan vi nu slutte, at \(P(1), P(2), P(3),...\) er sande.

At dette udtømmer de naturlige tal, er en grundlæggende egenskab ved disse. Inden for aksiomatiseringen af aritmetikken kaldes induktionsprincippet for Peanos femte aksiom; det er ækvivalent med, at enhver ikke-tom delmængde af de naturlige tal har et mindste element.

Et eksempel på anvendelse af induktion er beviset for, at \(P(n): 1+2+...+n = n(n+1)/2\) er sandt for alle \(n\geq 1\). 1) \(P(1)\) er sandt, da \(1 = 1\cdot 2/2\). 2) Antag, at \(P(n)\) er sandt. Så er \(1+2+...+n+n+1 = n(n+1)/2+n+1 =(n+1)(n+2)/2\), hvilket viser, at \(P(n+1)\) er sandt.

Se også Peanos aksiomsystem.