Induktsioonisammu

Induktsioonisamm on osa matemaatilise induktsiooni tõestusmeetodist. Baasjuhtum kinnitab, et lause P(n) kehtib algväärtuse puhul, tavaliselt n0 (kõige sagedamini 0 või 1). Induktsioonisamm näitab, et kui lause P(n) on tõene, siis P(n+1) on tõene. Täieliku tõestuse jaoks peetakse kas baas- ja induktsioonisammu koos või, kui on vaja, ka tugevamat lähenemist.

Induktsioonisammu sõnastus on: iga n ≥ n0 korral kehtib P(n) → P(n+1). Kui need kaks sammu on tõestatud, siis P(n) kehtib kõikide n ≥ n0 jaoks. Induktsioon on seega tõestusviis, kus tõde „levib edasi” ühe võrra.

Erinevus tugevast induktsioonist seisneb esitusviisis: tugeva induktsiooni puhul eeldatakse, et P(k) on tõene kõigi k ≤ n korral ning seejärel näidatakse, et P(n+1) on tõene. Mõlemat lähenemist kasutatakse sõltuvalt lause olemusest.

Näide: tõestame lause, et 1 + 2 + ... + n = n(n+1)/2 kõigi n ≥ 1 puhul. Baas: n = 1 korral vasakul on 1 ja paremal 1. Induktsioonisamm: eeldusel, et 1+...+n = n(n+1)/2, siis 1+...+n+(n+1) = n(n+1)/2 + (n+1) = (n+1)(n+2)/2, mis on soovitud tulemus. Seega kehtib lause kõigi n jaoks.