Induktionsbevis
Wikipedia
Induktionsbevis är en viktig bevismetod inom matematiken.
Typiskt används metoden för att bevisa att något är sant för alla naturliga tal. Man kan då beskriva metoden på följande sätt:
- Kontrollera att påståendet är sant för talet n = 0.
- Antag att påståendet är sant för n = m, där m är ett godtyckligt naturligt tal.
- Visa att påståndet då även gäller för n = m + 1.
Nu vet vi att: Påståndet är sant för n = 0. Då är det även sant för n = 1 och då är det sant för n = 2 och så vidare.
Metoden kan generaliseras och tillämpas för andra mängder än de naturliga talen, nämligen alla välordnade mängder. En variant av indirekt bevis för naturliga tal är också
- Bevisa att om en sats är sann för alla naturliga tal k < n, så är den även sann för n.
- Man kan då dra slutsatsen att satsen är sann för alla naturliga tal.
Denna formulering liknar mer den generella formen av induktion.
Vanligtvis formuleras principen för matematisk induktion som ett axiom för de naturliga talen, se till exempel Peanos axiomsystem. Det är emellertid möjligt att inom vissa formella system härleda principen från andra antaganden, till exempel
- Mängden av naturliga tal är välordnad.
