Bevis

bevistyper

Det finnes flere typer matematiske bevis. Matematiske bevis er sentrale for å etablere en sannhet i faget, men de er også viktige i læringsprosessen ved at de skal skape innsikt og forståelse. Det har liten verdi å pugge sekvenser i et bevis om man ikke forstår tankene som ligger til grunn for sekvensene og hva man har som mål.

Direkte bevis

Ideen bak et direktebevis er at P impliserer Q.

1) Anta at P er sant.

2) Bruk P til å vise at Q er sant

Eksempel 1:

Utsagn: Summen av to oddetall er et partall.

Ett oddetall er et tall som ikke er delelig på 2 og kan generelt skrives som n= 2k + 1 der $k \in \N.$ To forskjellige oddetall kan skrives som $n_1=2k_1+1$ og $ n_2= 2k_2 + 1 (k_1 \neq k_2)$

Summen av $n_1$ og $n _2$: $n_1 + n_2 = 2k_1+1 + 2k_2 + 1 = 2(k_1+k_2)+2 = 2(k_1+k_2+1)$

som er et tall delelig på 2, altså et partall.

Eksempel 2:

Påstand: ”Kvadratet av et partall er også et partall.”

Dersom vi plukker ut et vilkårlig tall p i mengden Z vet man at x = 2p alltid er et partall.

Vi kvadrerer og får:

Hvilket er et bevis for påstanden.

Bevis ved motsigelse

Indirekte bevis- kontrapositivt bevis

Ideen er å anta at konklusjonen er feil, og derved at premissene er feil. Det må da være feil at konklusjonen er feil.

Dersom man vil bevise at a medfører b, <math>a \Rightarrow b</math> er det likeverdig med å bevise

<math>ikke \quad b \Rightarrow \quad ikke \quad a</math>.

Eksempel:

Dersom produktet av to positive reelle tall er større en 100 så er minst en av faktorene større enn 10.

<math>xy > 100 \Rightarrow x \geq 10 \vee y \geq 10 </math>

Nå antar vi at begge faktorene er mindre eller lik 10:

Hvilket er et bevis for påstanden i begynnelsen av eksemplet.

Bevis ved moteksempel

Dersom man påstår: ” alle nordmenn har blå øyner” kan det være fornuftig å bruke denne teknikken dersom man ønsker å bevise at påstanden er feil.

Det er nok at man finner en nordmann som ikke har blå øyner for å bevise at ”alle nordmenn har blå øyner” er feil.

Man kan motbevise en påstand med et eksempel, men man kan aldri bevise en påstand med et eksempel (ikke med to eller flere heller).

Eksempel:

Vi har følgende påstand:

<math>x^2 =y^2 \Rightarrow x = y</math>

Sagt med ord utrykker påstanden at dersom kvadratet av et tall er lik kvadratet av et annet tall så impliserer det at det ene tallet er lik det andre tallet.

Dersom x = 2 og y = 2 stemmer begge sider av implikasjonen, men dersom x = 2 og y = - 2 stemmer bare venstre side. Høyre side er feil, og man har bevist at påstanden er feil.

Induksjonsbevis

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

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

Dersom

1. induksjonsgrunnlaget <math>U(n_0)</math> er sann

og

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

så er <math>U(n)</math> sann for alle <math>n \geq n_0.</math>

Prinsippet for induksjonsbevis illustreres enklest via et konkret eksempel: La oss si at vi ønsker å bevise formelen

\[ \sum_{i=1}^{n}i=\frac{n(n+1)}{2}\, \qquad \forall n \in \mathbb{N} \]

Trinn 1

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

Trinn 2 (induksjonstrinnet)

I induksjonstrinnet antar vi at formelen gjelder for en bestemt verdi av n, si <math>n=k</math> og utleder deretter via kjente regneregler at formelen også gjelder for <math>n=k+1</math>. Dersom vi lykkes, vil dette indusere en dominoeffekt: Fra trinn 1 vet vi at formelen gjelder for <math>n=1</math> og trinn 2 sikrer at formelen gjelder for <math>n=2</math> (og på samme måte at formelen gjelder for <math>n=3</math> etc.).

I det konkrete eksempelet vil induksjonstrinnet se slik ut:

Vi antar at formelen er riktig for <math>n=k</math>:

\[ \sum_{i=1}^{k}i=\frac{k (k+1)}{2} \]

Vi undersøker så summen når <math>n=k+1</math> ved å bruke denne antagelsen:

\[ \begin{aligned} \sum_{i=1}^{k+1}i &= \sum_{i=1}^{k}i + (k+1) \\ &= \frac{k(k+1)}{2} + (k+1) \\ &= \frac{(k+1)(k+2)}{2} \end{aligned} \]

Her ser vi altså at dersom formelen er riktig for <math>n=k</math>, så vil formelen være riktig for <math>n=k+1</math>. 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 en del eksempler.

Eksempel 1:

La oss se litt nærmere på eksemplet over, denne gangen uten bruk av summetegn:

\[ 1 + 2 + 3 + \ldots + \ n = \frac{n (n+1)}{2} \]

Tallet n skal være et positivt helt tall.

Først undersøker man induksjonsgrunnlaget: Når n = 1 blir høyre side lik venstre side.

I induksjonstrinnet antar vi først at formelen er riktig for n = k:

\[ 1 + 2 + 3 + \ldots + k = \frac{k (k+1)}{2} \]

Deretter undersøker vi summen for n = k + 1, ved å bruke antagelsen:

\[ \begin{aligned} 1 + 2 + 3 + \ldots + k + (k+1) &= \frac{k (k+1)}{2} + (k+1) \\ &=(k+1) ( \frac{k}{2} + 1) \\ &= \frac{(k+1)(k + 2)}{2} \end{aligned} \]

Vi ser at den siste linjen er høyresiden i formelen når n = k + 1. Altså er beviset fullført.

Eksempel 2:

Bevis formelen

\[ 1^2 + 2^2 + 3^2 +.....+ n^2 = \frac{n(n+1)(2n+1)}{6} \qquad n \in \mathbb{N} \]

Man finner først om induksjonsgrunnlaget er sant. Når n = 1 er venstre side lik <math> 1^2 = 1,</math> og høyre side er <math> \frac{1 \cdot 2 \cdot 3}{6} = 1.</math> Induksjonsgrunnlaget er dermed sant, begge sider er lik 1 for n=1.

I induksjonstrinnet antar vi først at formelen er riktig for n = k:

\[ 1^2 + 2^2 + 3^2 + \ldots + k^2 = \frac{k(k+1)(2k+1)}{6} \]

Så undersøker vi summen for n = k + 1 ved å bruke antagelsen:

\[ \begin{aligned} 1^2 + 2^2 + 3^2 +.....+ k^2 + (k+1)^2 &= \frac{k(k+1)(2k+1)}{6} + (k+1)^2 \\ &= (k+1) [ \frac{k(2k+1)}{6} + (k+1) ] \\ &= (k+1) \frac{k[2k+1 + 6(k+1)]}{6} \\ &= \frac{(k+1)[2k^2+7k+6]}{6} \\ &= \frac{(k+1)[2(k+2)(k + \frac{3}{2})]}{6} \\ &= \frac{(k+1)(k+2)(2k + 3)}{6} \\ \end{aligned} \]

Den siste linjen er høyresiden i formelen når n = k + 1.

Q.E.D. (quod erat demonstrandum)

Eksempel 3:

Bevis derivasjonsregelen $(x^n)' = nx^{n-1}.$

I induksjonsgrunnlaget viser vi først at formelen gjelder for n = 1:

Høyre side: $n \cdot x^{n-1} = 1 \cdot x^0 =1$

Venstre side $(x^1)'= x' =1$

Induksjonsgrunnlaget er sann: Linjen y = x har stigningstall 1.

I induksjonstrinnet antar vi som vanlig at formelen er riktig for n = k:

\[ (x^k)' = kx^{k-1} \]

Vi viser så at formelen holder for n = k + 1, ved å bruke antagelsen sammen med regelen for derivering av et produkt:

\[ \begin{aligned} (x^{k+1})' &= (x \cdot x^k)' \\ &= x^k + x \cdot k \cdot x^{k-1} \\ &= x^k + kx^k \\ &= (1+k)x^k \end{aligned} \]

Q.E.D.

Eksempel 4:

Bevis at $n^3-4n+6$ er delelig på 3 når n er et ikke-negativt heltall.

1. Induksjonsgrunnlag: n=0 gir $n^3-4n+6 = 6$, som er delelig på 3.

2. Induksjonstrinnet: Anta at $n^3-4n+6$ er delelig på 3 når n = k. Med n = k + 1 får vi

\[ \begin{aligned} (k+1)^3 -4(k+1) + 6 &= (k+1)(k^2 + 2k + 1)- (4k + 4) + 6 \\ &= (k^3 + 2k^2 + k + k^2 + 2k + 1) - 4k + 2 \\ &= (k^3 -4k + 6) + 3(k^2 + k - 1) \end{aligned} \]

Den første parantesen er delelig på 3, i følge antagelsen for n = k. Den andre inneholder faktoren 3. Sammen gir dette at hele uttrykket er delelig på 3.

Se også:

Bevisføring