Et enkelt bevis

Mange finner bevis vanskelig. Her er rom for spørsmål vedrørende bevis, og for å dele dine bevis med andre. Vi tenker først og fremst videregående nivå, men det er ingen begrensninger her.

Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa

Svar
Toppris
Maskinmester
Maskinmester
Innlegg: 383
Registrert: 03/02-2005 19:32
Sted: Stavanger

Bare for å oppmuntre til litt bevisoppgaver

Bevis følgende:
[tex]\sum_{i=1}^n i^2=\frac{n(n+1)(2n+1)}{6}[/tex]
sEirik
Guru
Guru
Innlegg: 1551
Registrert: 12/06-2006 21:30
Sted: Oslo

Den tar vi med induksjon :-) Jeg har lyst til å kjøre på med et fullstendig bevis denne gangen.

------
(1) Vi definerer påstanden P(n): [tex]\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}[/tex]

Vi vil bevise at [tex]\forall n \in {\mathbb N}:\ {\rm P} (n)[/tex].

(2) Vi sjekker om påstanden stemmer for n = 1:

[tex]\sum_{i=1}^1 i^2 = 1^2 = 1[/tex]

[tex]\frac{1(1+1)(2 \cdot 1 + 1)}{6}= \frac{6}{6} = 1[/tex]

Vi ser altså at P(1) stemmer.

(3) Vi antar at P(m) stemmer. Det betyr at

[tex]\sum_{i=1}^m i^2 = \frac{m(m+1)(2m+1)}{6}[/tex]

Vi legger til [tex](m+1)^2[/tex] på begge sider:

[tex]\sum_{i=1}^m i^2 + (m+1)^2 = \frac{m(m+1)(2m+1)}{6} + (m+1)^2[/tex]

På venstresiden kan vi trekke inn [tex](m+1)^2[/tex] i sumuttrykket:

[tex]\sum_{i=1}^{m+1} i^2 = \frac{m(m+1)(2m+1)}{6} + (m+1)^2[/tex]

Vi skriver om høyresiden:

[tex]\sum_{i=1}^{m+1} i^2 = \frac{m(m+1)(2m+1) + 6(m+1)^2}{6}[/tex]

[tex]\sum_{i=1}^{m+1} i^2 = \frac{2m^3 + m^2 + 2m^2 + m + 6m^2 + 12m + 6}{6}[/tex]

[tex]\sum_{i=1}^{m+1} i^2 = \frac{2m^3 + 9m^2 + 13m + 6}{6}[/tex]

[tex]\sum_{i=1}^{m+1} i^2 = \frac{(x+1)(x+2)(2x+3)}{6}[/tex]

[tex]\sum_{i=1}^{m+1} i^2 = \frac{(x+1)(x+1 + 1)(2(x+1)+1)}{6}[/tex]

Vi setter [tex]n = m+1[/tex].

[tex]\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}[/tex]

Ergo P(n).

(4) Vi ser at P(1) stemmer, og av (3) vet vi at da må også P(2) stemme, og da må P(3) stemme osv. Vi har at P(n) stemmer for alle naturlige tall n.
sEirik
Guru
Guru
Innlegg: 1551
Registrert: 12/06-2006 21:30
Sted: Oslo

Og så kommer neste:

[tex]\sum_{i=1}^n i^3 = \left [ \frac{n(n+1)}{2} \right ]^2[/tex]
Charlatan
Guru
Guru
Innlegg: 2499
Registrert: 25/02-2007 17:19

Bruker samme metoden som forrige mann her: (hadde ikke klart det uten)

[tex]\sum_{i=1}^n i^3 = (\frac{n(n+1)}{2})^2[/tex]

[tex]\sum_{i=1}^1 i^3 = 1^3 = 1[/tex]

[tex](\frac{1(1+1)}{2})^2 = 1 [/tex]
Riktig for 1.

Vi antar at beviset stemmer for m:

[tex]\sum_{i=1}^m i^3 = (\frac{m(m+1)}{2})^2[/tex]

Vi plusser på (m+1)^3 på begge sider som gir oss:

[tex]\sum_{i=1}^{m+1} i^3 = (\frac{m(m+1)}{2})^2+(m+1)^3[/tex]

[tex]\sum_{i=1}^{m+1} i^3 = \frac{m^2(m+1)^2}{4}+(m+1)(m+1)^2[/tex]

[tex]\sum_{i=1}^{m+1} i^3 = (\frac{m^2}{4}+m+1)(m+1)^2[/tex]

[tex]\sum_{i=1}^{m+1} i^3 = \frac{1}{4}(m^2+4m+4)(m+1)^2[/tex]

[tex]\sum_{i=1}^{m+1} i^3 = \frac{1}{4}(m+2)^2)(m+1)^2[/tex]

[tex]\sum_{i=1}^{m+1} i^3 = \frac{(m+2)^2(m+1)^2}{4}[/tex]

m+1=n

[tex]\sum_{i=1}^{n} i^3 = \frac{(n+1)^2(n)^2}{4}[/tex]

[tex]\sum_{i=1}^{n} i^3 = (\frac{n(n+1)}{2})^2[/tex]

Og det fullfører beviset :)
Charlatan
Guru
Guru
Innlegg: 2499
Registrert: 25/02-2007 17:19

Hvorfor kan man anta at beviset gjelder for m?
ingentingg
Weierstrass
Weierstrass
Innlegg: 451
Registrert: 25/08-2005 17:49

Det er det induksjon handler om.

Vi skal bevise en påstand som skal gjelde f.eks for alle n.
Målet med induksjon er å vise at hvis det gjelder for n så vil det og gjelde for n+1. I tillegg må man vise at man kan begynne et sted f.eks på 1.
Da får man:

Regelen er gyldig for n = 1.

Og siden den er gyldig for n+1 hvis den er gyldig for n vil det si at:

Den er gyldig for:
n=2
n=3
n=4
osv
Charlatan
Guru
Guru
Innlegg: 2499
Registrert: 25/02-2007 17:19

Ah, så det er som å bare la n = 1, og siden beviset gjelder for n+1 må det gjelde for 1+1, og hvis n=1+1=2 da er n=2, og da må det gjelde for n+1 = 2+1 = 3, n=3
Magnus
Guru
Guru
Innlegg: 2286
Registrert: 01/11-2004 23:26
Sted: Trondheim

Jau!
daofeishi
Tyrann
Tyrann
Innlegg: 1486
Registrert: 13/06-2006 02:00
Sted: Cambridge, Massachusetts, USA

Her er en ikke-induktv løsningsmetode. Jeg går etter prinsippet "kan det løses uten induksjon, så løs det uten" ;)
Charlatan
Guru
Guru
Innlegg: 2499
Registrert: 25/02-2007 17:19

Det var en ganske kul måte å løse det på.

Det blir vel verre når summene er mer kompliserte
ingentingg
Weierstrass
Weierstrass
Innlegg: 451
Registrert: 25/08-2005 17:49

Eg synes induksjon er en fin måte å vise ting.
Er verre å bruke selvmotsigelsesbevis. Ofte vanskelig å vite hva og om du har bevist noko. Når du så er i mål er det sjelden du har blitt noko særlig klokere av det.
daofeishi
Tyrann
Tyrann
Innlegg: 1486
Registrert: 13/06-2006 02:00
Sted: Cambridge, Massachusetts, USA

Vel, det er akkurat det jeg mener om mange induksjonsbevis. De er "mekaniske," i det at de vil produsere et fullt ut logisk korrekt bevis, men ikke vil gi noen innsikt i hvorfor det er korrekt.

Jeg synes ofte selvmotsigelsesbevis er veldig belysende. Her er et litt ikke-matematisk eksempel:
Teorem: "Jorden er ikke flat eller uendelig stor."
Bevis: Anta at jorden er flat og uendelig stor. Vi vet at vi kan fly i én retning, uten å havne utenfor en kant og ende opp på samme punkt som vi startet etter finitt tid. Selvmotsigelse. Jorden kan derfor ikke være flat eller uendelig stor.

Det finnes selvsagt induksjonsbevis som kommer til kjernen av akkurat hvorfor ting er som de er - et eksempel kan jo være beviset for antall elementer i potensmengden P(S) til et sett S. [tex]|P(S)| = 2^{|S|}[/tex]. Hvorfor dette stemmer skjønner man intuitivt fra induksjonsbeviset.

Hvis du ser på formelen overfor er det en formel som er enkel å bevise dersom du kjenner den. Hvis du ikke gjør det hjelper ikke induksjon deg en døyt.
ingentingg
Weierstrass
Weierstrass
Innlegg: 451
Registrert: 25/08-2005 17:49

Må si meg delvis uenig med deg der. Problemet med selvmotsigelsesbevis er at du ikke kommer noe nærmere hva som er korrekt svar.

Ta eksempelet ditt med jorden? har du noen mer kunnskap om hvordan jorden ser ut eller hvilken størrelse den har?. Selvsagt ikkje. Du har bare vist at den ikke er uendelig stor eller flat.

Og når selvmotsigelsesbevisene er lange, er det utrolig vanskelig å vite at det faktisk er den første antagelsen som er feil og ikkje noko annet.

Induksjonsbevis kan selvsagt være mekaniske, viss svaret er gitt, men ofte er det mulig å "tippe" på enkle eksempler eller prøve for n = 1, 2, 3 og se en sammenheng.
For eksempel for å finne Taylorpolynom er det jo ypperlige å derivere et par ganger, tippe en formel å så vise den ved hjelp av induksjon.

Heldigvis har begge to rett, dette er jo faktisk et eksempel på at flere måter kan være korrekte i matematikken.
Charlatan
Guru
Guru
Innlegg: 2499
Registrert: 25/02-2007 17:19

Jeg har alltid fundert på hvor grunnleggende skal man gjøre et bevis. Hvor mange antakelser kan man gjøre. Man må jo alltid bygge bevisene sine på andre bevis, og aksiomer. For eksempel, et bevis for nykommere er jo å bevise at hvis x er oddetall, og y er oddetall, så er xy et oddetall.
Men her går vi ut ifra at et oddetall kan skrives som 2n+1. Her har vi gått ut ifra flere ting. Som at det går an å addere sammen to tall, at 2*(hvilket som helst hetall) = et partall. Ethvert bevis som er mer komplisert enn andre, bygger jo på de aller mest grunnleggende bevisene. Så, til poenget: Er det definert hvilke ting som kan være naturlig å anta når man fører bevis?
ingentingg
Weierstrass
Weierstrass
Innlegg: 451
Registrert: 25/08-2005 17:49

Som regel kan man anta alt som ligger på "nivået under".

Eks:
Vil man vise derivasjonsregler antar man de vanlige reglene for lim
Skal man vise integrasjonsregler antar man derivasjonsregler.

Når det kommer til lærebøker på universitetet så vil det ofte bli vist helt fra aksiomene og definisjonene. I analyskurs er det for eksempel vanlig med å begynne med å vise at de reelle tallene eksisterer. At + og * er veldefinert. osv.
Svar