Induksjonsbevis

[Quent]

Sitter her og styrer med induksjonsoppgaver fra R2-pensumet, og kunne trengt litt hjelp. Jeg kom til induksjonsdelen av boka tidligere i dag, så dette er fortsatt ganske nytt for meg og jeg håper bare at jeg har gjort det rett. Så vidt jeg ser har jeg det.

Det dreier seg om oppgave 6.291 fra Cosinus R2, og oppgaven lyder:

Vis ved induksjon at
[tex]n^3 - 4n + 6[/tex]

er delelig med 3 for alle naturlige tall [tex] n \ge 0[/tex]

Fikk den omsider till, men er ikke fornøyd med løsningen min som jeg synes er rotete og temmelig fæl.

Jeg begynner med å observere at når n=0, så er verdien 6, som åpenbart er delelig med 3. Når n=1 blir verdien 3, som jo også er delelig med 3 (:P).

Da sier jeg at

[tex]k^3-4k + 6=3q[/tex] for en gyldig verdi k.
Dette kan stilles opp slik:
[tex]k((k^2-4)) + 6 = 3q[/tex] noe som betyr at enten så er [tex]k[/tex] delelig med 3, eller så er [tex]k^2-4[/tex] delelig med 3.

Vi setter [tex]n=(k+1)[/tex].
[tex](k+1)^3 - 4(k+1)+6 = k^3 + 3k^2 - k + 3 = k(k^2 + 3k - 1) +3 =k(k^2 - 3 + 3k + 3 - 1) + 3 = k((k^2-4) + 3k + 3) + 3[/tex]

Vi kikker på den siste likheten her, [tex]k((k^2-4) + 3k + 3) + 3[/tex]. Som vi så tidligere så må enten [tex](k^2-4)[/tex] eller k være delelig med 3, noe som medfører at [tex]k((k^2-4)+3k+3))[/tex] er delelig med 3.
[tex](k+1)^2 - 4(k+1) + 6[/tex] er da også delelig med 3, og vi har bevist at [tex]n^3 - 4n + 6[/tex] er delelig med 3 for alle naturlige tall [tex] n \ge 0[/tex].

Satser på at noen har en langt smartere strategi for å gjøre dette (så lenge det jeg har gjort er korrekt), og er spent på å høre.

[Nebuchadnezzar]

Vi observerer at det stemmer når [tex]n=1[/tex]

[tex]n^3-4n+6[/tex]

[tex]1^3 - 4\cdot 1 + 6 = 1 - 4 + 6 = 3 [/tex]

Vi antar nå at det stemmer for [tex]n=k[/tex], og skal vise at det stemmer for [tex]n=k+1[/tex]

[tex](k+1)^3-4(k+1)+6[/tex]

[tex](k+1)^3-4k+2[/tex]

[tex](k^3+3k^2+3k+1)-4k+2[/tex]

[tex]k^3+3k^2-k+3[/tex]

[tex]k^3+3k^2-k+3+(3-3)+(-3k+3k)[/tex]

[tex]3k^2+3k-3+(k^3-4k+6)[/tex]

[tex]3(k^2+k-1)+(k^3-4k+6)[/tex]

Vi ser greit at den første parentesen er delelig med 3. Ved å bruke induksjonshypotesen vår ser vi også at siste del er delelig på 3.

Q.E.D

EDIT:

[tex]n^3-4n+6[/tex]

6 er åpenbart delelig på 3. vi må dermed vise at [tex]n^3-4n[/tex] er delelig på 3.

[tex]n^3-4n=(n-2)n(n+2)[/tex]

Som vi greit kan se alltid er delelig på 3. Blant tre annenhver påfølgende heltatt, vil alltid ett av disse være delelig på 3.

1 * 3 * 5 , 2 * 4 * 6 , 3 * 5 * 7

Q.E.D

Eventuelt bruke induksjonsmåten jeg viste over.

[Quent]

Oi, kjapt svar. Takker. Ser at fremgangsmåten i induksjonsbeviset ble mye penere ja. Allikevel kom jeg meg vel i land jeg også?

[Nebuchadnezzar]

Nja, ikke helt.

Problemet ditt er at du ikke bruker hypotesen om at formelen stemmer for n=k. Det er fundamentalt i et induksjonsbevis.

1. Vise at det stemmer for en gitt verdi. (Ofte n=1 , men ikke alltid)
n=1
2. Anta at det stemmer for n=k
3. Vise at det stemmer for n=k+1, når vi antar at det stemmer for n=k

[Quent]

Gjør jeg ikke? Jeg sier jo:

Jeg begynner med å observere at når n=0, så er verdien 6, som åpenbart er delelig med 3. Når n=1 blir verdien 3, som jo også er delelig med 3 (:P).

Da sier jeg at

[tex]k^3-4k + 6=3q[/tex] for en gyldig verdi k.

Hvorfor holder ikke det? Jeg viser jo (vel, jeg nevner) at det er sant når n=1, antar så at det stemmer når n=k og viser så at det da også stemmer når n=(k+1). Hva skulle jeg gjort annerledes?

[Nebuchadnezzar]

Rotete formulert, vanskelig å vite hvordan du faktisk beviser noe.
Slik jeg ser det så er det viktig når man fører bevis, og være klokkeklar på hva man skal vise, og hvordan.

Slik jeg ser det ligger feilen din i at.

[tex]k((k^2-1)+3k+3)[/tex] ikke er det samme som induksjonshypotesen din der du bruker at [tex]k((k^2-4))[/tex] er delelig på [tex]3[/tex].

[Quent]

Greit, skjønner hva du mener om formuleringen. Men, hvis [tex]k(k^2-4)[/tex] er delelig med 3, betyr ikke det da at [tex]k((k^2-4) + 3k + 3)[/tex] også vil være det? Hvis k er delelig med 3, går det jo opp. Hvis [tex](k^2-4)[/tex] er delelig med 3 (setter [tex]k^2-4=3p[/tex] for enkelhets skyld), så må vel [tex]\frac{(3p) + 3k +3}{3} = p + k + 1[/tex]. Og da er jo n=k+1 delelig med 3?

[Nebuchadnezzar]

Du vet ikke at [tex]k^2-4[/tex] er delelig på [tex]3[/tex]. Og forøvrig så er det heller ikke det =)

[Quent]

Vel, slik har jeg tenkt:

Når n=k, [tex]k((k^2-4)) + 6[/tex]. Da må jo enten k eller (k^2-4) være delelig med 3. k vil vel være delelig med 3 når k inneholder en 3-faktor, mens (k^2-4) vil være delelig med 3 dersom 3 ikke er en faktor i k. Er det et ugyldig argument?

[Nebuchadnezzar]

Når jeg sier at (k^2-4) ikke er delelig på 3, så mener jeg at du ikke kan si at

(k^2-4)=3q

Rett og slett fordi den ikke er delelig på 3 for alle verdier av k. Og dermed kan du heller ikke bare anta det. Er dessverre ikke slikt et induksjonsbevis fungerer.

Resten av det du skriver er helt rett. Bare at du ikke nødvendigvis kan bruke det i et induksjonsbevis.

[Quent]

Jeg brukte nå kun [tex](k^2-4)=3p[/tex] for å tydliggjøre forklaringen min, ikke som en del av beviset. Poenget mitt er at [tex]k(k^2-4)[/tex] er delelig med 3, og da må [tex]k((k^2-4)+3k+3) + 3[/tex], som jeg får når n=(k+1), også være det. Jeg har da vist at funksjonen er delelig med 3 for n=0 (som oppgaven spør om), n=1, antatt at den er delelig med 3 når n=k, og dermed vist at den da også er delelig med 3 når n=(k+1). Jeg har ikke antatt at (k^2-4) er delelig med 3 for alle k, bare at enten så er k delelig med 3, eller så er (k^2-4) delelig med 3. Prøver forresten ikke å være påståelig på at jeg har rett, bare å forstå hva jeg eventuelt gjør feil, for akkurat nå skjønner jeg ikke helt.

edit: Ble noen små redigeringer der.
edit: Egentlig ganske mange redigeringer.

[Nebuchadnezzar]

Du kan ikke bare si at k((k^2-4)+3k+3) er delelig på 3 bare fordi k(k^2-4) er det.

Du kan gjøre det slik som jeg har gjort det under.

[tex]k(k^2-4)[/tex]

[tex](k+1)((k+1)^2-4)[/tex]

[tex](k+1)(k^2+2k+1-4)[/tex]

[tex]k^3+2k^2-3k+(k^2+2k-3)[/tex]

[tex]k^3+3k^2-k-3[/tex]

[tex]k(k^2-4)+3k-3[/tex]

[tex]k(k^2-4)+3(k-1)[/tex]

Du må bruke nøyaktig det som står i unduksjonshypotesen din, ikke bare noe som ligner. Eller har litt mye tretall, så du tror at det stemmer.

=)

[Gustav]

Steg 2: Anta at [tex]k^3-4k+6[/tex] er delelig med 3. Det medfører at enten [tex]k[/tex], [tex]k-2[/tex] eller [tex]k+2[/tex] er delelig med 3. Skal vise at [tex](k+1)^3-4(k+1)+6[/tex] er delelig med 3 som er det samme som å vise at [tex](k+1)((k+1)^2-4)[/tex] er delelig med 3. Vi omskriver det siste til [tex](k+1)(k-1)(k+3)[/tex].

Det er nå 3 tilfeller som må sjekkes:

i) Dersom k er delelig med 3 er k+3 delelig med 3, som er en faktor i uttrykket over.

ii) Dersom k-2 er delelig med 3 er k+1=k-2+3 delelig med 3, som også er en faktor.

iii) Dersom k+2 er delelig med 3 er k-1=k+2-3 delelig med 3, som igjen er en faktor.

Ergo er [tex](k+1)(k-1)(k+3)[/tex] delelig med 3, og vi er ferdige.

[Quent]

Du kan ikke bare si at k((k^2-4)+3k+3) er delelig på 3 bare fordi k(k^2-4) er det.

Jeg antar det er her jeg misforstår. Jeg skjønner ikke helt hvorfor du ikke kan si det? Hvis faktor k er delelig med 3 i k(k^2-4), må den jo også være det i k((k^2-4)+3k+3)? Og hvis (k^2-4) er delelig med 3 (som den vil for de k som ikke er delelige med 3), så må jo også ((k^2-4)+3k+3 være det? Og jeg innbiller i alle fall at jeg viste at en av de to faktorene må være delelige med 3 i beviset mitt? Er det der jeg har gjort feil?

Legger meg nå, og leser igjennom tråden nøye i morgen. Kikker litt mer i boka hvis jeg fortsatt ikke har forstått. Har ingenting å innvende mot noen av bevisene som har blitt presentert av deg eller plutarco, prøver bare å forstå bristen i mitt eget bevis.

[Nebuchadnezzar]

Jeg mener bestemt at du ikke kan si det. Jeg sier ikke at det er feil, men for å løse oppgaven som et induksjonsbevis MÅ du bruke induksjonshypotesen. Det gjør ikke du, du bare bruker noe som ligner. Da kunne du like gjenre løst oppgaven som plutarco viste.

Feil er det ikke, men er feil i forhold til å løse oppgaven som et induksjonsbevis =)