matematikk.net

Bare for å oppmuntre til litt bevisoppgaver

Bevis følgende:
[tex]\sum_{i=1}^n i^2=\frac{n(n+1)(2n+1)}{6}[/tex]

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.

Og så kommer neste:

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

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

Hvorfor kan man anta at beviset gjelder for m?

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

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

Jau!

Her er en ikke-induktv løsningsmetode. Jeg går etter prinsippet "kan det løses uten induksjon, så løs det uten"

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

Det blir vel verre når summene er mer kompliserte

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.

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.

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.

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?

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.