Matematisk induksjon

Frå Wikipedia – det frie oppslagsverket
Gå til: navigering, søk

Matematisk induksjon er ein metode nytta for matematiske bevis, vanlegvis for å vise at eit visst uttrykk gjeld for alle naturlege tal. 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.

Døme[endre | endre wikiteksten]

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

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.

\frac{n(n+1)}{2} \Rightarrow \frac{(1)(1+1)}{2}=1\,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 n=k+1.

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

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

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

Reknar ut høgresida:


= \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:

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 n\ge1.