Bevis og bevisteknikk

I denne artikkelen gir vi en kortfattet introduksjon til forskjellige bevis og bevisteknikker.

Et matematisk bevis består av en påstand og en kjede argumenter som ender opp med å slå fast om påstanden er riktig eller uriktig.

Vi tar bare for oss påstander som enten er riktige eller uriktige, såkalte utsagn. Eksempler på slike påstander er “vinkelsummen i en trekant er 180 grader” og “april har 31 dager”, som er henholdsvis et sant og et usant utsagn. Påstander som “jordbær er godt” eller “Gerhardsen gjorde en god jobb som statsminister” er subjektive, og vi kan ikke bevise om de er riktige eller uriktige.

Når vi formulerer en påstand, må vi passe på å være nøyaktige, slik at påstanden ikke kan misforstås. Vanlig språk er ofte dårlig egnet til å formulere påstander fordi dagligtalen vår er full av unøyaktigheter. Ta for eksempel påstanden “Mellom 20 og 25 finnes tre heltall med to primfaktorer”. Betyr “tre heltall” nøyaktig tre heltall eller minst tre heltall? Betyr “to primfaktorer” nøyaktig to primfaktorer, eller minst to primfaktorer? Betyr “mellom 20 og 25” at 20 og 25 regnes med eller ikke?

For å unngå slike unøyaktigheter, er det utviklet en egen matematisk terminolog som er fri for tvetydigheter. For eksempel kan vi uttrykke at “et tall, n, er mellom 20 og 25″ som $n \in [20, 25]$, som betyr at 20 og 25 skal telle med, eller $n \in \langle 20, 25 \rangle$, som betyr at 20 og 25 ikke skal telle med. En påstand som utelukkende er uttrykt gjennom matematiske symboler, kan imidlertid være tung å lese, så i denne artikkelen bruker vi vanlig språk når det ikke kan føre til misforståelser. For eksempel uttrykker vi den nevnte påstanden som “Det finnes nøyaktig tre heltall, $n \in[20, 25]$, som består av nøyaktig to primfaktorer.”

En beviskjede kan være kort eller lang.

Eksempel 1:

Påstand: 4 er et primtall.
Bevis for at påstanden er uriktig: 4 kan faktoriseres som 2 · 2, og er derfor ikke et primtall.

Påstand: Det finnes ingen heltallige, x, y, z, slik at xn + yn = zn når n > 2.
Beviset for denne påstanden er 150 sider langt og tok 7 år å utarbeide. Påstanden sto ubevist i over 350 år.

I eksempel 1 er det er underforstått at vi vet hva et primtall er, og at vi vet at et tall som kan faktoriseres ikke er et primtall. Det vil som regel være slik at vi i et bevis må anta at en del begreper er kjent på forhånd.

Ikke alle påstander kan bevises, og det kan bevises at enkelte påstander ikke kan bevises.

Så skal vi se litt nærmere på forskjellige typer bevis.

Uttømmende bevis

En av de enkleste bevisformene er uttømmende bevis, der vi viser at en påstand er riktig ved å undersøke alle muligheter som inngår i påstanden.

Eksempel 2:

Påstand: Det finnes nøyaktig tre heltall, $n \in[20, 25]$, som består av nøyaktig to primfaktorer.

Bevis: Vi faktoriserer heltallene mellom 20 og 25:

20 = 2 · 2 · 5

21 = 3 · 7

22 = 22 ·  11

23 = 23

24 = 2 · 2 · 2 · 3

25 =5 · 5

Vi ser at 21, 22 og 25 og ingen andre av tallene oppfyller kravet, og påstanden er derved bevist.

Oppgave 1:

Bevis følgende påstand: Det finnes nøyaktig ett heltall, $n \in[20, 25]$, som består av nøyaktig fire primfaktorer.

Se løsningsforslag

Dersom antall muligheter som må undersøkes blir mange, blir uttømmende bevis tungvint, og helt umulig hvis en påstand gjelder et uendelig antall muligheter, noe som ofte er tilfelle.

Hvis et uttømmende bevis ikke undersøker alle muligheter, er det ugyldig. Det er en vanlig feil å tro at en har bevist en påstand ved å ramse opp noen eksempler på at den er riktig.

Eksempel 3:

Påstand: Alle tall på formen 2p – 1 er primtall hvis p er et primtall.

Ugyldig bevis: Vi tester påstanden for en del primtall, p:

22 – 1 = 3. Primtall.

23 – 1 = 7. Primtall.

25 – 1 = 31. Primtall.

27 – 1 = 127. Primtall.

213 – 1 = 8191. Primtall.

217 – 1 = 131071. Primtall.

219 – 1 = 524287. Primtall.

Skulle metoden i eksempel 3 ført fram, måtte vi testet alle primtall som finnes. Og siden det finnes uendelig mange, lar det seg ikke gjøre. Påstanden er heller ikke riktig, som vi skal se i eksempel 5.

Eksempel 4:

Påstand: Summen av tre etterfølgende heltall er alltid lik tre ganger det midterste tallet. For eksempel er

3 + 4 + 5 = 3 · 4

11 + 12 + 13 = 3 · 12

(-13) + (-12) + (-11)  = 3(-12)

Ugyldig bevis: Vi tester påstanden for 10 000 sekvenser av tre etterfølgende heltall i et regneark, og finner ut at påstanden stemmer.

Påstanden i eksempel 4 er riktig, men uansett hvor mange eksempler vi prøver ut i et regneark, vil vi ikke få et et gyldig bevis. Vi sannsynliggjør imidlertid påstanden, noe som betyr at den er vel verd å utforske nærmere, og at vi kanskje kan finne et bevis for den. Som vi skal se i eksempel 11, kan vi bekrefte denne påstanden ved et enkelt, algebraisk bevis.

Bevis ved moteksempel

Det er altså ikke nok å bare sjekke en del av mulighetene som inngår for å bevise at en påstand er riktig. Derimot er det nok med ett enkelt moteksempel for å bevise at en påstand er uriktig, altså motbevise den.

Eksempel 5:

Påstand: Alle tall på formen 2p – 1 er primtall hvis p er et primtall.

Moteksempel: 11 er et primtall, men 211 – 1 = 2047 er ikke er et primtall. 2047 kan faktoriseres som 23 · 89.

Oppgave 2:

Bevis at følgende påstand er uriktig: Alle sammensatte tall større enn hundre består av minst tre primfaktorer.

Se løsningsforslag

Eksempel 6:

Påstand: Alle primtall er oddetall.

Moteksempel: 2 er et primtall, men ikke et oddetall.

Påstanden i eksempel 6 er gyldig for alle andre primtall enn 2. Det finnes altså uendelig mange tall den er riktig for, men bare ett den ikke er riktig for. Allikevel betyr dette ene moteksempelet at påstanden er uriktig. Med en liten modifikasjon blir imidlertid påstanden riktig: “Alle primtall unntatt 2 er oddetall”.

Dueslagprinsippet

Et enkelt bevis som går ut på opptelling, er det såkalte dueslagprinsippet: Hvis m objekter blir fordelt på n avdelinger, og m > n, vil minst én avdeling inneholde mer enn ett objekt. Hvis det for eksempel er 110 duer i et dueslag med 100 seksjoner, må det finnes seksjoner med mer enn 1 due.

Eksempel 7:

Påstand: Hvis det største antall hår et menneske kan ha på hodet er 150 000, vil det i en by med 200 000 innbyggere finnes noen som har nøyaktig samme antall hår.

Bevis: Siden det er flere hoder(m=200 000) enn maksimalt antall hår (n=150 000), sier dueslagprinsippet at det finnes mennesker som har nøyaktig samme antall hår.

 

Oppgave 3:

Vi roter etter sokker innerst i klesskapet, der det ligger 5 forskjellige par. Hvor mange må vi rote fram for å være sikre på å ha to like?

Se løsningsforslag

Kontrapositivt bevis

Vi har to påstander, A og B. Hvis A medfører B, konkluderer et kontrapositivt bevis med at  ikke-B medfører ikke-A.

Eksempel 8:

Alle sauene til Ola Oppigarden er svarte.

Her medfører påstand A (en sau tilhører Ola Oppigarden) påstand B (sauen er svart).

Påstand ikke-B (en sau er ikke  svart) medfører da ikke-A (sauen tilhører ikke Ola Oppigarden).

Det er imidlertid ikke slik at hvis A medfører B, vil B medføre A.

Eksempel 9:

Alle sauene til Ola Oppigarden er svarte. Men hvis vi ser en sau som er svart (påstand B), trenger den ikke tilhøre Ola Oppigarden (påstand A).

Påstanden i neste eksempel er en variant av påstanden i eksempel 3, men denne påstanden er riktig, uten at vi går inn på beviset.

Eksempel 10:

Det er slik at hvis n er et sammensatt tall (påstand A), er 2n – 1  et sammensatt tall (påstand B).

Et kontrapositivt bevis sier da at hvis 2n – 1 ikke er et sammensatt tall (påstand ikke-B), er n ikke et sammensatt tall (påstand ikke-A).

“Ikke sammensatt tall” er det samme som “primtall”, så vi har altså at:
Hvis 2n – 1 er et primtall, er n et primtall.

En påstand som er bevist, kalles gjerne et teorem, og en påstand som umiddelbart følger av et teorem kalles en korollar. Vi har altså:

Teorem: hvis n er et sammensatt tall, er 2n – 1  et sammensatt tall.

Ved kontrapositivt bevis følger da:

Korollar: Hvis 2n – 1 er et primtall, er n et primtall.

Hvis vi feilaktig prøver å si at B medfører A hvis A medfører B, får vi den uriktige påstanden fra eksempel 3.

Algebraisk bevis

Hvis vi skal bevise en påstand der vi ikke kan bruke et uttømmende bevis, kan et algebraisk bevis være et alternativ. I et algebraisk bevis bruker vi i stedet for tall symboler som er allmenngyldige.

Eksempel 11:

I eksempel 4 framsatte vi en påstand om at summen av tre etterfølgende heltall alltid er lik tre ganger det midterste tallet.

Det finnes uendelig heltall, så et uttømmende bevis er utelukket, og vi bruker et algebraisk bevis:

Kaller vi tallet i midten for a, vil sekvensen av tre etterfølgende tall bestå av a-1, a og a+1. Summen av disse blir (a – 1) + a + (a + 1) = a + a + a – 1 + 1 = 3a. Vi ser at uansett hvilken verdi a representerer, blir summen tre ganger denne verdien. Påstanden er derved bevist.

Eksempel 12:

Påstand: Summen av to partall er et partall.

Det finnes uendelig mange partall, så et uttømmende bevis er utelukket, og vi bruker et algebraisk bevis:

Et partall er et tall på formen 2t, der t er et helt tall. Summen av to heltall kan skrives som 2n + 2m = 2(n + m) = 2(n + m). Siden n + m er et heltall, ser vi at produktet er på formen 2t, og derved et partall.

I eksempel 12 har vi brukt 2n som symbol for det ene tallet og 2m som symbol for det andre. Hadde vi brukt samme symbol for begge, for eksempel 2t, ville det betydd at de to tallene var like. Vi har følgende prinsipp:

To tall som kan være ulike må representeres med forskjellige symboler.

Det er en vanlig feil blant elever å bruke samme symbol for to tall som kan være ulike.

Eksempel 13:

Uriktig påstand: Produktet av to partall er et kvadrattall.

Uriktig bevis: Et partall er et tall på formen 2t, der t er et helt tall. Produktet av to partall kan skrives som 2t · 2t = 2 · 2 · t · t = 22 · t2 = (2t)2. Og vi ser at produktet kan skrives som kvadratet av 2t.

Problemet er at t er brukt som symbol for to tall som kan være ulike. Vi har egentlig bare bevist det opplagte, at et tall multiplisert med seg selv er et kvadrattall. Med forskjellige symboler får vi 2m · 2n = 2 · 2 · m · n = 22 · m · n, som ikke trenger være et kvadrattall hvis m og n er ulike.

Men vi sier ikke at to tall representert med forskjellige symboler nødvendigvis må være ulike. Det er mulig at de er ulike, men det er også mulig at de er like. Beviset i eksempel 5 er like gyldig for to forskjellige tall, for eksempel 2 + 4, som for to like tall, for eksempel 2 + 2.

Oppgave 4:

Bevis at summen av to oddetall er et partall.

Se løsningsforslag

Bevis ved selvmotsigelse

I et bevis ved selvmotsigelse antar vi at det motsatte av det vi skal bevise er riktig, og demonstrerer at dette fører til en selvmotsigelse. Denne prosessen kalles også “reductio ad absurdum”.

Eksempel 14:

Påstand: Det finnes ingen hele, positive tall, a og b, slik at a2b2 = 10.

Bevis: Vi antar det motsatte, at det faktisk finne to slike tall, og viser at dette fører til en selvmotsigelse.

Vi starter med å bruke tredje kvadratsetning baklengs på venstre side, og får
(a + b)(ab) = 10.

10 kan skrives som produktet 5 · 2. Setter vi dette inn i likningen over, får vi

(a + b)(ab) = (5)(2) = 10.

Vi må altså ha
a + b = 5
ab = 2

Summerer vi de to likningene, får vi 2a + 0b = 7, det vil si at a = 3,5.

a er altså ikke et heltall, noe som er en selvmotsigelse siden vi i utgangspunktet forutsatte at både a og b skulle være heltall.

10 kan også skrives som produktet 10 · 1. Da får vi

(a + b)(ab) = (10)(1) = 10.

Vi må altså ha
a + b = 10
ab = 1

Summerer vi de to likningene, får vi 2a + 0b = 11, det vil si at a = 5,5.

a er heller ikke her et heltall, og vi har igjen en selvmotsigelse.

10 kan ikke skrives som et produkt av positive heltall på noen andre måter, og påstanden er derved bevist ved selvmotsigelse.

I eksempel 14 benyttet vi også prinsippet fra et uttømmende bevis. Det fantes to måter å skrive 10 som et produkt av heltall på, og vi tok for oss begge to.

Oppgave 5:

Finn feilen i følgende resonnement:

Vi påstår at det ikke finnes hele, positive tall, a og b, slik at a2b2 = 12.

Som bevis bruker vi selvmotsigelse, etter prinsippet fra eksempel 7:

12 kan skrives som produktet 4 · 3. Da har vi

(a + b)(ab) = (4)(3) = 12.

Vi må altså ha
a + b = 4
ab = 3

Summerer vi de to likningene, får vi 2a + 0b = 7, det vil si at a = 3,5.

a er altså ikke et heltall, noe som er en selvmotsigelse siden vi i utgangspunktet forutsatte at både a og b skulle være heltall.

12 kan også skrives som produktet 12 · 1. Da har vi

(a + b)(ab) = (12)(1) = 12.

Vi må altså ha
a + b = 12
ab = 1

Summerer vi de to likningene, får vi 2a + 0b = 13, det vil si at a = 6,5.

a er heller ikke her et heltall, og vi har igjen en selvmotsigelse.

Påstanden er derved bevist ved selvmotsigelse.

Se løsningsforslag

Induksjonsbevis

Et induksjonsbevis brukes typisk i forbindelse med påstander om heltall, og går i to trinn. Vi tar utgangspunkt i en påstand, U(n), som gjelder for alle nn0

I trinn 1 etablerer vi induksjonsgrunnlaget, det vil si at vi fastslår at U(n) er sann for startverdien n0

Trinn 2 kalles induksjonstrinnet, her viser vi at hvis U(n) er sann, er U(n+1) sann. 

Av trinn 2 følger da videre at hvis U(n+1) er sann, er U((n+1)+1) = U(n+2) sann, hvis U(n+2) er sann, er U((n+2)+1) = U(n+3) sann, og så videre. Denne logikken kan vi følge videre mot uendelig, og påstanden er derfor bevist for alle nn0

Eksempel 15:

Vi skal bevise at summen av alle hele tall fra og med 1 til og med n er lik $\frac{\displaystyle n(n + 1)}{\displaystyle 2}$.

For eksempel er $1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = \frac{\displaystyle 10(10 + 1)}{\displaystyle 2} = 55$

I trinn 1 viser vi da at påstanden er riktig for n0 = 1, det vil si at summen av tallene fra og med 1 til og med 1 er 1. Og formelen gir $\frac{\displaystyle 1(1 + 1)}{\displaystyle 2} = 1$, så påstanden er riktig for n0 = 1.

Formelen vi skal bevise sier at hvis

$1 + 2 + 3 + \cdots + {\color{brown}n} = \frac{\displaystyle {\color{brown}n}({\color{brown}n} + 1)}{\displaystyle 2}$

er

$1 + 2 + 3 + \cdots + n + ({\color{brown}{n + 1}}) = \frac{\displaystyle {(\color{brown}{n + 1}})\big(({\color{brown}{n + 1}}) + 1\big)}{\displaystyle 2}$

(For å tydeliggjøre har vi markert siste ledd i rekka med brunt.)

Regner vi ut telleren i brøken, ser vi at den blir

$\frac{\displaystyle (n + 1)(n + 2)}{\displaystyle 2}$

I trinn 2 skal vi vise at dette er riktig. Vi har altså

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

Vi adderer et nytt ledd på begge sider av likhetstegnet:

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

Vi skriver uttrykket på høyre side som en enkelt brøk:

$\frac{\displaystyle n(n + 1) + 2(n + 1)}{\displaystyle 2}$

Vi regner ut parenteser og trekker sammen like ledd:

$\frac{\displaystyle n^2 + 3n + 2}{\displaystyle 2}$

Til slutt faktoriserer vi andregradsuttrykket:

$\frac{\displaystyle(n + 1)(n + 2)}{\displaystyle 2}$

Som er det uttrykket formelen sa vi skulle få. Når formelen er gyldig for n, er den altså gyldig for n + 1. Siden vi i trinn 1 viste at formelen var gyldig for n = 1, er den følgelig gyldig for n + 1 = 2, og siden den er gyldig for n = 2 er den gyldig for n = 2 + 1 = 3, og så videre mot uendelig.

Oppgave 6:

Bevis at

$1^2 + 2^2 + 3^2 + \cdots + n^2 = \frac{\displaystyle n(n + 1)(2n+1)}{\displaystyle 6}$

for alle n ≥ 1.

Se løsningsforslag

Kilder