Anbefaler deg å se resten og, den første er bare en slags kort introduksjon. Er også mye andre videoer og poster om dette temaet. Men det viktigste er bare å jobbe en del med stoffet.
http://www.youtube.com/watch?v=4vNsOeCvyS0
Bevisføring er nok noe nytt for deg, men er uten tvil en av de aller største og viktigste områdene innenfor matematikken.
Derfor er det skuffende at det er såpass lite fokus på dette i den videregående skole, og mye større fokus på formelpugging. Som i mine øyne gjør mer skade enn nytte.
Jeg kan prøve å forklare deg induksjonsbevis, og det kommer kanskje til å bli et langt svar, men da kan jeg i det minste refferere til denne i fremtiden.
Det er mange ulike måten en kan bevise ting på.
Direkte bevis: Her følger vi en rekke logiske steg, som fører frem til en ønsket konklusjon. Kan ta et banalt eksempel under
Vis at dersom Ole bor i bergen, bor også Ole i Norge.
Igjen, dette er banalt enkelt. Men bare for å understreke poenget
1) Bergen er en by som ligger i Norge. <- Logisk steg
Siden Ole bor i bergen, og bergen ligger i Norge, betyr dette at Ole bor i Norge.
Her trekker vi en konklusjon, etter ett eller flere logiske steg.
Selvmotsigelsesbevis: Om vi vil vise frem våre latinkunnskaper så heter dette
proof ad absurdum praksis et bevis hvor en igjen fører en rekke logiske steg og kommer kommer frem til en motsigelse. Vi kan også si at vi antar at noe stemmer, også utfører vi en rekke logiske steg, og viser at det ikke stemmer. La oss ta et klargjøre med et kort eksempel under
Er følgende setning sann? [tex]P(n) = n^2 + n + 41[/tex]
Danner primtall for alle [tex]n \geq0[/tex]
Her kan vi anta at polynomet danner primtall for alle [tex]n[/tex]. Om vi setter inn tall finner vi tilslutt ut at
[tex]P(41) = 41^2 + 41 + 41 = 41(41 + 1 + 1)[/tex]
Som ikke er et primtall. Altså har vi kommet frem til en motsigelse! [tex]P(n)[/tex] genererer ikke primtall for alle [tex]n[/tex]!
Kontrapositivt bevis: Dette høres ganske fancy ut, men er ikke så veldig komplisert heller. I det direkte beviset så viser vi for eksempel at A fører til B. Dersom A er sann, så er det logisk at B også er sann.
Med et kontrapositivt bevis, så viser vi det motsatte.
Dersom A ikke er sann fører dette til B heller ikke er sann.
For eksempel
Alle partall er delelig på 2. A = alle partall og B = delellig på 2.
[tex]3[/tex] er ikke et partall, altså er 3 ikke delelig med 2.
Her ser vi at ikke A fører til ikke B.
Nå som vi har vist tre bevismetoder, så skal vi se nærmere på den siste. Litt merkelig at de tre ovenfor ikke er vektlagt mer. Da bevis ved induksjon kan ofte være litt vanskelig å forstå.
Det er også litt rart at en begynner å innføre slike litt tøffe bevis i skolen, uten å snakke noe særlig om bevisføring før. Den videregående skolen er som kjent preget av mye formeltygging, og da kan overgangen til å bevise ting virke brå. Dermed mener jeg at bevismetodene ovenfor er enklere å forstå, og burde vært vektlagt mer og tidligere enn induksjon.
Likevel gir induksjonsbevis opphav til noen kreative algebraproblem, som sikkert er mye av grunnen til at den er tatt med i R2. En kort innføring er gitt under.
Bevis via induksjon: Prinsippet her er at vi først viser at det stemmer for en eller annen verdi, eller størrelse. Her blir [tex]1[/tex] ofte valgt, men det er ikke nødvendig vi kunne like gjerne valgt [tex]2[/tex].
La oss nå anta at vi har vist at det stemmer for [tex]n=1[/tex]. Det neste steget er å anta at det stemmer for et vilkårlig tall, for ikke å forvirre dette med [tex]n[/tex] brukes ofte [tex]k[/tex]. Så nå antar vi at det stemmer for en tilfeldig verdi. Beviset går nå ut på å vise at dersom det stemmer for dette tilfeldige tallet, så stemmer det også for det neste tallet.
Det bler en liten munnfull, men tenk litt over det =)
La oss si at vi har gjort induksjonsbeviset. Vi vet at det stemmer for [tex]n=1[/tex] og vi har vist at
dersom det stemmer for en tilfeldig verdi, stemmer det også for den påfølgende verdien
[tex]k \qquad[/tex] og [tex]\qquad k+1[/tex]
Men så spør du, stemmer formelen for [tex]n=5[/tex]?
Vel det stemmer for [tex]n=5[/tex], dersom det stemmer for [tex]n=4[/tex].
Det stemmer for [tex]n=4[/tex], dersom det stemmer for [tex]n=3[/tex]
Det stemmer for [tex]n=3[/tex], dersom de stemmer for [tex]n=2[/tex]
Det stemmer for [tex]n=2[/tex] dersom det stemmer for [tex]n=1[/tex]
Men vi har vist at det stemmer for [tex]n=1[/tex]. !
Dermed stemmer det også for [tex]n=5[/tex]. Så med denne tankegangen, kan vi vise at det stemmer for alle verdier.
Alternativt kan vi gå andre veien. Vi har vist at det stemmer for [tex]n=1[/tex], altså stemmer det også for [tex]n=2[/tex]. Som igjen betyr at det stemmer for [tex]n=3[/tex] osv.
Dette er tankegangen bak induksjon. En sammenlikner det ofte med fallende dommino. Første brikke faller [tex](n=1)[/tex] andre brikke faller, tredje faller også videre. Vi gjør det klarere med et enkelt eksempel
Vis at [tex]1 \, + \, 2 \, + \, 3 \, + \, ... \, + \, n = \frac{n(n+1)}{2}\ [/tex]
holder for alle [tex]\ n\geq 1[/tex]
Her er det logisk å vise at det stemmer for [tex]n=1[/tex]. Hvorfor? Jo fordi dette er den første verdien oppgaven sier at formelen holder for. Vi vet ikke at formelen ovenfor stemmer, dette er noe vi skal undersøke.
For å vise at formelen stemmer for [tex]n=1[/tex] setter vi inn [tex]n=1[/tex] på høyre side(HS) og [tex]n=1[/tex] på venstre side (VS)
[tex]VS = 1[/tex]
[tex]HS = \frac{1(1+1)}{2} = \frac{2}{2} = 1[/tex]
Altså stemmer det for [tex]n=1[/tex] siden VS=HS. Neste steget blir å anta at det stemmmer for et eller annet tilfeldig tall. La oss bare anta at det stemmer for tallet [tex]u[/tex]. Altså at [tex]n=u[/tex]. Vi antar dermed at
[tex]1 \, + \, 2 \, + \, 3 \, + \, ... \, + \, u = \frac{u(u+1)}{2}\ [/tex]
stemmer. Nå skal vi vise at dersom det stemmer for [tex]u[/tex], så stemmer det for tallet som kommer etter [tex]u[/tex]. Eller også bedre kjent som [tex]u+1[/tex]. Målet blir å vise at VS=HS når [tex]n=u+1[/tex], ved å bruke antakelsen om at det stemmer når [tex]n=u[/tex].
Nå ser vi på høyre og venstre side seperat, siden vi enda ikke vet om de er like. Vi ønsker å enten vise at høyre side kan omformes til venstresiden, eller omvendt. Det klassiske er at vi alltid må bruke antakelsen om det stemmer for tallet før, altså [tex]n=u[/tex]. Vi ser på venstre side først
[tex]VS \, = \, 1 \, + \, 2 \, + \, 3 \, + \, ... \, + \, u + [u+1] [/tex]
Her kan vi allerede nå bruke induksjonshypotensen vår. Vi har antatt at det stemmer for [tex]n=u[/tex]. Som er det samme som at
[tex]1 \, + \, 2 \, + \, 3 \, + \, ... \, + \, u = \frac{u(u+1)}{2}\ [/tex]
Som igjen er det samme som venstresiden vår. Vi kan dermed bytte ut dette uttrykket. Som gir oss
[tex]VS \, = \, 1 \, + \, 2 \, + \, 3 \, + \, ... \, + \, u + [u+1] [/tex]
[tex]VS \, = \left( \, 1 \, + \, 2 \, + \, 3 \, + \, ... \, + \, u \right) + [u+1] [/tex]
[tex]VS \, = \left( \frac{u(u+1)}{2} \right) + [u+1] [/tex]
[tex]VS \, = \left( \frac{u(u+1)}{2} \right) + \frac{2(u+1)}{2} [/tex]
[tex]VS \, = \frac{(u+1) \left( u + 2 \right)}{2} [/tex]
I siste steget så har vi bare trekt ut den felles faktoren [tex]u+1[/tex], og satt på felles brøkstrek. Vi ser nå på høyre side når [tex]n=u+1[/tex]. Da får vi
[tex]HS =\frac{[u+1]([u+1]+1)}{2} = \frac{(u+1)(u+2)}{2}[/tex]
Nå ser vi at HS=VS. Og beviset vårt er ferdig. Det vi nå har vist er at det stememer for [tex]n=1[/tex] og at dersom det stemmer for [tex]n=u[/tex], så stemmer det for det påfølgende tallet [tex]n=u+1[/tex]. I korte trekk går de fleste induksjonoppgaver som følger.
1) Vis at det stemmer for [tex]n=1[/tex] (Må ikke være [tex]1[/tex])
2) Anta at det stemmer for et tilfeldig tall [tex]n=k[/tex].
3) Vis at dersom det stemmer for [tex]n=k[/tex], så stemmer det for [tex]n=k+1[/tex]
Steg 3 varierer fra oppgave til oppgave, men i praksis går dette steget alltid ut på å vise at VS=HS, gjennom noen smarte algebraiske steg.
Nå kan du prøve deg på oppgaven, eller lese litt mer om undiksjon først. Er ikke så vanskelig etter ett par oppgaver. =)
EDIT: Takker Svinepelz, var litt rask på avtrekkeren der jeg. Fikser det opp =)
)