Bevis

[Bernoulli]

Er det noen her som kan bevise på en enkel og grei måte at

1 + 2 + ... + n = n(n+1)/2.

Jeg vet hvordan man gjør det, men vil se om det finnes noen andre måter å gjøre det på.

[oro2]

Skriver opp summen forlengs og baklengs, tilsammen n ledd i hver rekke.
S = 1 + 2 + 3 + ... + (n-2) + (n-1) + n
S = n + (n-1) + (n-2) + ... + 3 + 2 + 1

Summerer rekkene (1. ledd i 1. rekke med 1. ledd i 2. rekke... osv).
2S = (1+n) + (2+n-1) + (3+n-2) + ... + (n-2+3) + (n-1+2) + (n+1)
2S = (n+1) + (n+1) + (n+1) + ... + (n+1) + (n+1) + (n+1)
2S = n(n+1)
S = n(n+1)/2

[joolae]

Det går an å løse dette ved matematisk induksjon også.. men jeg husker ikke hvordan
Noen som vet det?

[ThomasB]

Induksjon:
1. Gjelder formelen for n=1?

1 = 1(1+1)/2 = 1
Ok, det gjør den!

2. Hvis den gjelder for en n, gjelder den da også for neste n?
Vi antar da at:
1 + 2 + 3 + ... + n = n(n+1)/2

Er da formelen for n+1 riktig?
1 + 2 + 3 + ... + n + (n+1) = (n+1)((n+1)+1)/2 <--- Stemmer dette?

For å sjekke dette skriver vi om venstre side av likningen ovenfor, ved å benytte antakelsen om at formelen stemmer for n:
(1 + 2 + 3 + ... + n) + (n+1) = (n(n+1)/2) + (n+1) = (n[sup]2[/sup] + n + 2n + 2)/2 = (n+1)(n+2)/2 = (n+1)((n+1)+1)/2 <---- Det samme som da vi satte (n+1) rett inn i formelen

Dermed har vi vist at dersom formelen gjelder for en n, gjelder den også for den neste. Ettersom n=1 er riktig, beviser dette hele formelen.

[Bernoulli]

Jeg kan egentlig ikke skjønne at induksjon kan brukes som et fullgodt bevis for matematiske utsagn. Det eneste du trenger er å vise at formelen gjelder for n= "en eller annen startverdi" og for n=k+1 for en vilkårlig k. I mine øyne ligger svakheten i at man antar at formelen gjelder for k. Og da er det som regel bare å legge til k+1 på begge sider av ligningen, og du får det ønskede uttrykket.

Man kan egentlig "bevise" mange åpenbart usanne ting vha induksjon. En tidligere matte-foreleser jeg hadde, "beviste" at alle elefanter er rosa vha induksjon! (men jeg husker dessverre ikke fremgangsmåten)

[LGO]

Induksjon som bevis, fungerer på grunn av egenskapene til tallene. Uansett hvilket tall jeg sier, kan man si det neste tallet i rekkefølgen. Tallene fortsetter uendelig. Når man derfor viser at noe gjelder for f.eks. tallet 1, og at det gjelder generelt for to påfølgende tall, har man vist at det må gjelde for alle de naturlige tallene. Bruker man derimot induksjon på ting som ikke har tallenes egenskap, kan det nok bli feil. Kanskje det var det som gjorde at din lærer kunne "bevise" at alle elefanter er rosa?

[ThomasB]

Jeg kan egentlig ikke skjønne at induksjon kan brukes som et fullgodt bevis for matematiske utsagn.

Induksjon er gyldig og fullgodt bevis. Et induksjonsbevis er analogt med følgende premisser og slutning:

1. Du står på ett trinn i en stige.
2. Hvis du står på ett trinn, kan du nå det neste. (At man står på et trinn er her bare en antakelse.)

Slutning:
Du kan nå et hvilket som helst trinn i stigen.

Dette er sant bare dersom både punkt 1 og 2 er sanne. Hvis ikke 1 er sann, beviser ikke 2 noenting. Hvis 1 er sann derimot, gir 2 at du kan nå neste trinn. Deretter bruker du 2 så mange ganger du vil på hvert nye trinn du har nådd.

Hvis du ser nøye etter i trinn 2 i beviset over, ser du at jeg ikke bare har lagt til (n+1) på begge sider av formelen. Dette hadde ikke bevist noe. På venstre side har jeg lagt til (n+1) til det som allerede sto der. På høyre side har jeg byttet ut (n) med (n+1) i formelen. Det var ikke gitt at dette ble det samme, men ved å skrive det om så vi at det ble likt.

Kall summen av de n første tallene for S(n). Jeg har altså vist at S(n+1) = S(n) + (n+1) for den gitte formelen S(n) = n(n+1)/2

Ble det klarere nå? Det bør ikke være noen tvil om gyldigheten av induksjonsbevis, men de fleste pleier å måtte bruke litt tid på å forstå det de første gangene de ser det.

[Bernoulli]

Dette er ikke første gangen jeg er borti induksjon, og det er ikke vanskelig å skjønne hvordan man bruker den. Men for meg virker det som om induksjon er noe man tyr til når man ikke kan bevise ting på en annen (og mer pålitelig) måte.

Kan si det på denne måten: selv om det er solskinn og fint vær den første dagen i sommerferien og en eller annen vilkårlig dag midt i ferien, så betyr ikke det at det blir solskinn også neste dag, eller hva?

Problemet er som sagt at man antar (gjentar: antar) at formelen e.l. er gyldig for en vilkårlig n. Man bruker altså formelen selv til å bevise at den faktisk er sann!

[Gjest]

Hvordan kan man trene seg i å regne seg frem til sumformler av rekker?

Feks finn summen av : S = x - x² + x³ - .... + xª

[ThomasB]

Kan si det på denne måten: selv om det er solskinn og fint vær den første dagen i sommerferien og en eller annen vilkårlig dag midt i ferien, så betyr ikke det at det blir solskinn også neste dag, eller hva?

Nei det gjør det ikke. Dette er en logisk gal slutning. Det du blander sammen med her er det såkalte "induksjonsproblemet" i filosofien, man kan ikke gjøre en logisk slutning fra ett spesialtilfelle til det generelle tilfelle. Men i induksjonsbeviset gjør vi IKKE denne feilen:

I trinn to over beviser vi faktisk helt generelt at "hvis det regner en dag så regner det den neste dagen også".

Problemet er som sagt at man antar (gjentar: antar) at formelen e.l. er gyldig for en vilkårlig n. Man bruker altså formelen selv til å bevise at den faktisk er sann!

Nei, man antar IKKE at den gjelder for en vilkårlig n, man antar at den gjelder for EN n.

Man bruker heller ikke formelen selv til å vise at den er sann. Det man gjør er å sjekke om formelen oppfyller en nødvendig betingelse som er helt uavhengig av formelen selv.

Les nøye så skal jeg se om jeg klarer å overbevise deg:
La S(n) være en vilkårlig funksjon av n, som oppfyller ligningen:

S(n) = S(n-1) + n

Dette er en rekursiv ligning, og verdien av S(n) er entydig bestemt av en eller annen startverdi, sett f.eks. S(0) = 0
Påstand: S(n) er summen av de n første tallene.

Bevis:
S(0) = 0, som er oppfylt.
Dersom vi kjenner summen av de (n-1) første tallene, får vi summen av de n første tallene ved å legge til n. Ettersom S oppfyller dette, må S være summen av de n første tallene.

Bare si ifra hva du lurer på her, jeg gir meg ikke før jeg har klart å overbevise deg

Og hvis noen skulle være i tvil: Et induksjonsbevis ER logisk gyldig, og like godt som et annet bevis. Det som er vanskelig er å sette opp betingelsen i trinn to, som en formel må oppfylle.

Eksempler:
La f.eks. funksjonen f(n) være n! (n fakultet)
Da oppfyller f følgende TO betingelser:
1. f(0) = 1
2. f(n) = n*f(n-1)

La funksjonen g(n) være summen av de n første kvadrattallene, 1+4+9+...+n[sup]2[/sup]. Da oppfyller g:
1. g(0) = 1
2. g(n) = g(n-1) + n[sup]2[/sup]

Hvis du har en formel for g, er det tilstrekkelig å sjekke de to betingelsene ovenfor. Legg merke til at punkt to er et generelt krav, det MÅ gjelde for ALLE n (og det er det som tilsvarer at "regn en dag medfører regn neste dag")



Puh, dette ble langt, blir visst litt engasjert av slike diskusjoner...

[ThomasB]

Sjekk også denne korte formuleringen av prinsippet om matematisk induksjon
Principle of mathematical induction