Matematisk Induksjon

Dette er gjort med å vise at det første uttrykket i ei uendeleg rekkje av uttrykk er sann, og så vise at eit vilkårleg uttrykk i den uendelege rekkja er sann, og til slutt det neste uttrykket i rekkja.

Denne metoden kan utvidast til å bevise uttrykk som gjeld meir generelle velfunderte strukturar, slik som for tre i mengdelære. Denne generaliseringa vert kalla strukturell induksjon og vert nytta i matematisk logikk og datavitskap.

Her skal vi vise at summen for alle naturlege tal kan skildrast som:

${\displaystyle 1+2+3+...+n={\frac {n(n+1)}{2}}}$ , der n er eit naturleg tal.

Første skritt er å vise at uttrykket gjeld for 1.

${\displaystyle {\frac {n(n+1)}{2}}\Rightarrow {\frac {(1)(1+1)}{2}}=1\,}$  då n=1. Dermed har vi vist at uttrykket gjeld for n=1.

Neste skritt er å vise at om uttrykket gjeld for n=k, medfører det at uttrykket òg gjeld for ${\displaystyle n=k+1}$ .

• Antar: ${\displaystyle 1+2+3+...+k={\frac {k(k+1)}{2}}}$ 

Legg til k + 1 på begge sider og får:

${\displaystyle 1+2+\cdots +k+(k+1)={\frac {k(k+1)}{2}}+(k+1)}$ 

Reknar ut høgresida:

${\displaystyle ={\frac {k(k+1)}{2}}+{\frac {2(k+1)}{2}}={\frac {(k+2)(k+1)}{2}}={\frac {(k+1)(k+2)}{2}}={\frac {(k+1)((k+1)+1)}{2}}.}$ 

Dermed har vi:

${\displaystyle 1+2+\cdots +(k+1)={\frac {(k+1)((k+1)+1)}{2}}}$ 

og beviset er ferdig. Vi har no vist at uttrykket gjeld for n=1, og at om uttrykket gjeld for k, medfører det at uttrykket òg gjeld for k+1. Induksjonsprinsippet seier dermed at uttrykket gjeld for alle naturlege tal ${\displaystyle n\geq 1}$ .