Induksjonsbevis

Bevis ved induksjon er delt i to trinn, induksjonsgrunnlaget og induksjonstrinnet.

La U(n) være et åpent utsagn som gjelder for alle\quad <tex> n \geq n_0</tex>

Dersom

1. induksjonsgrunnlaget<tex>\quad U(n_0)</tex> er sann

og

2. induksjonstrinnet\quad <tex>U(k) \Rightarrow U(k+1),\quad k\geq n_0 </tex> er sann,

så er U(n) sann for alle n ≥ n0.

Prinsippet for induksjonsbevis illustreres enklest via et konkret eksempel: La oss si at vi ønsker å bevise formelen <tex>\sum_{i=1}^{n}i=\frac{n(n+1)}{2}\,\forall n \in \mathbb{N}</tex>.

Steg 1

Det første vi gjør er å verifisere at formelen vi skal bevise gjelder for spesialtilfellet <tex>n=1</tex>. Dette er trivielt siden <tex>\sum_{i=1}^{1}i=1</tex> og <tex>\frac{1\cdot (1+1)}{2}=1</tex>; høyresiden er lik venstresiden.

Steg 2 (induksjonssteget)

I induksjonssteget antar vi at formelen gjelder for en bestemt verdi av n, si <tex>n=m</tex>, og utleder deretter via kjente regneregler at formelen gjelder for <tex>n=m+1</tex>. Dersom vi lykkes vil dette indusere en dominoeffekt; fra steg 1 vet vi at formelen gjelder for <tex>n=1</tex> og steg 2 sikrer at formelen gjelder for <tex>n=2</tex> (og på samme måte at formelen gjelder for <tex>n=3</tex> etc.).

I det konkrete eksempelet vil induksjonssteget se slik ut:

<tex>\sum_{i=1}^{m}i=\frac{m(m+1)}{2} \\ m+1+\sum_{i=1}^{m}i=m+1+\frac{m(m+1)}{2} \\ \sum_{i=1}^{m+1}i=\frac{(m+1)(m+2)}{2} </tex>

Her ser vi altså at dersom formelen er riktig for <tex>n=m</tex> vil formelen være riktig for <tex>n=m+1</tex>, og dette kompletterer induksjonsbeviset.

Denne "malen" for induksjonsbevis vil i prinsippet gjelde for alle problemer, dog vil det kunne oppstå ulike vanskeligheter for de spesifikke variasjonene, men disse er av "algebraisk" karakter. For å bli fortrolig med induksjon er man nødt til å regne gjennom endel eksempler.