Matematisk induksjonsbevis- R2 pensum

Her kan du stille spørsmål vedrørende problemer og oppgaver i matematikk for videregående skole og oppover på høyskolenivå. Alle som føler trangen er velkommen til å svare.

Moderatorer: Aleks855, Gustav, Nebuchadnezzar, Janhaa, DennisChristensen, Emilga

rembrandt
Descartes
Descartes
Innlegg: 425
Registrert: 10/11-2011 08:47

Hei folkens,

jeg sliter med matematisk induksjonsbevis og lurer på om dere kan gi meg tips til hvordan jeg kan mestre det emnet.

Jeg trenger virkelig gode tips slik at det sitter klistret i hjernen og jeg klarer å løse all slags oppgaver relatert til dette emnet.

Takk...
When men, even unknowingly, are to meet one day, whatever may befall each, whatever the diverging paths, on the said day, they will inevitably come together in the red circle.
svinepels
Descartes
Descartes
Innlegg: 411
Registrert: 19/12-2010 22:15
Sted: Oslo

Bachelor i matematiske fag NTNU - tredje år.
malef
Grothendieck
Grothendieck
Innlegg: 809
Registrert: 28/11-2007 16:24

Jeg har også slitt mye med induksjonsbevis. For meg løsnet det da jeg skjønte følgende:

Når man antar at formelen stemmer for n=k, så er uttrykket med k summen av alle leddene. Så det man gjør er bare å legge til enda et ledd (med n=k+1) og se hva man får etter litt algebra.

Jeg fikk veldig god hjelp av videoen svinepels linket til :)
rembrandt
Descartes
Descartes
Innlegg: 425
Registrert: 10/11-2011 08:47

Hei,

takk for tipsene, men jeg syns at det er fortsatt uklar. Jeg forstår litt av prinsippet, men det blir abstrakt når man kommer mot slutten. Kanskje dere kan tilføye noe...
When men, even unknowingly, are to meet one day, whatever may befall each, whatever the diverging paths, on the said day, they will inevitably come together in the red circle.
dan
Dirichlet
Dirichlet
Innlegg: 188
Registrert: 25/09-2010 16:38

Jeg foreslår du leser i boka di, og løser oppgaver. Hvis du lurer på noe konkret, kan du jo spørre om det.
Kork
von Neumann
von Neumann
Innlegg: 527
Registrert: 26/07-2011 18:44
Sted: Bergen

Mitt problem når jeg først skulle lære meg induksjon var jeg ikke stolte på mine egne resonnement, jeg kunne gå gjennom hele prosedyren i hodet om og om igjen men det tok meg forferdelig lang tid før jeg til slutt følte meg sikker på at tankegangen min var riktig.

Induksjon er noe man må gruble på ganske mye før det føles naturlig, så ikke gi opp, gå gjennom prinsippet eller spesifikke oppgaver i hodet gang på gang og begynn på nytt dersom du detter av. Til slutt vil det nok sitte.
Mathematics is the gate and key to the sciences.
viking
Dirichlet
Dirichlet
Innlegg: 168
Registrert: 19/10-2012 02:54

Hei,
Her er ett enkelt eksempel som du lett skjønner.
Hvor mange måter kan du arrangere en kø med mennesker?
Hypotese: En kø med N mennesker kan arrangeres på
1*2*3*...*N=N! måter.

Bevis ved induksjon:
a. Først tester vi for noen små tall for å sjekke denne påstanden:
1 i køen gir bare 1 måte; OK.
2 i køen: Vi kan ha Ole eller Nina først. Det blir 2 måter. 1*2=2; Fremdeles OK.
3 i køen: Tenk deg litt om. Det blir 1*2*3=3!=6; Fremdeles ok.

Her er nøkkelen til induksjon:
Hva skjer egentlig hvis vi har bevist det opp til ett tall M, og vi legger en person til køen. Fra (3) ovenfor har du sikkert allerede fått med deg at med en mer i køen på M mennesker, kan vi velge mellom (M+1) til å stå sist i køen. OK. Køen foran denne siste personen blir selvfølgelig uforandret, så det blir fremdeles (antageligvis) M! måter den kan arrangeres på.

Dette vil altså si at hvis påstanden er sann for M, så blir den slik for (M+1):
(M+1)*M!
Er dette det samme som (M+1)! ?
(M+1)*M=(M+1)*1*2*3*4*5*...*M. Vi bytter rundt og får
=1*2*3*4*5*...*M*(M+1)
Dette er jo bare definisjonen på (M+1)!, og beviset er fullført.

Som du ser har vi vist at det er sant for 1,2 og 3. Vi har også vist at hvis det er sant for 3, så
det være sant for 4. Og hvis det er sant for 4, så må der være sant for 5, Og hvis det er sant for 5 så må det...

Ferdigt.

Prøv å bevis at et oddetall pluss 2 er også ett oddetall med tilsvarende logikk. Det er ganske enkelt.
rembrandt
Descartes
Descartes
Innlegg: 425
Registrert: 10/11-2011 08:47

Hei,

beklager men jeg ble ikke klok av de forslagene over. Takker for at dere vil hjelpe, men det er ikke lett å sette seg inn i det. Den boken jeg bruker, som heter Sigma R2 er elendig til å forklare det emnet og lurer på om det er noen andre bøker som forklarer det bedre?

Ser frem til svar.

takk
When men, even unknowingly, are to meet one day, whatever may befall each, whatever the diverging paths, on the said day, they will inevitably come together in the red circle.
laustr
Cayley
Cayley
Innlegg: 54
Registrert: 06/01-2012 14:16

Jeg kan jo prøve meg med litt forklaring jeg også.
Prinsippet med induksjon er å vise at det gjelder for alle tall, når det først gjelder for ett.


Induksjonsbeviset består av to trinn
Ett grunntrinn og et induksjonstrinn
I grunntrinnet skal du vise at det stemmer for et gitt tall, for eks. 1
I induksjonstrinnet skal du anta at det stemmer for et tall k og bruke dette til å bevise at det då må stemme for k+1.

Som et eksempel så kan vi si at hypotesen vår er at [tex]S(n): \, 1+2+3+\cdots n= \frac{n\cdot(n+1)}{2}[/tex]

Vi begynner med grunnsteget og viser at det stemmer for ett gitt tall. I dette tilfellet 3.
Venstre side: [tex]1+2+3=6[/tex]
Høyre side: [tex]\frac{3\cdot(3+1)}{2}=6[/tex]
Vi ser dette stemmer og går videre til induksjonstrinnet

Vi antar at
[tex]S(k):\, 1+2+3+\cdots k= \frac{k\cdot(k+1)}{2}[/tex] stemmer.
Vi ser hva vi får viss vi setter n=k+1
[tex]S(k+1):\, 1+2+3+\cdots k+(k+1)=\frac{(k+1)\cdot(k+2)}{2}[/tex]
Viss vi nå antar at hypotesen vår stemmer og setter [tex]S(k)[/tex] inn i [tex]S(k+1)[/tex]

Vi får då
[tex]\frac{k\cdot(k+1)}{2}+(k+1)=\frac{(k+1)\cdot(k+2)}{2}[/tex]

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

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

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

Vi har då vist at det stemmer og dermed er hypotesen vår sann.
Vektormannen
Euler
Euler
Innlegg: 5889
Registrert: 26/09-2007 19:35
Sted: Trondheim
Kontakt:

Fin forklaring :)

Jeg har en liten ting å bemerke, som har med logikk å gjøre. Beviset ditt er ikke feil, men du gjør noe underveis som du kanskje ikke har tenkt over (?). Det er noe jeg ser veldig ofte, og som jeg selv har gjort tidligere.

Det er viktig å huske på at implikasjon ikke alltid går begge veier. At [tex]P \Rightarrow Q[/tex] betyr ikke nødvendigvis at [tex]Q \Rightarrow P[/tex].

Når du skriver [tex]\frac{k(k+1)}{2} + (k+1) = \frac{(k+1) \cdot (k+2)}{2}[/tex]
så antar du egentlig at likheten i S(k+1) gjelder, og så ser du hva det leder frem til. La oss kalle den ligningen for P. Du kommer frem til at [tex]\frac{(k+1) \cdot (k+2)}{2} = \frac{(k+1) \cdot (k+2)}{2}[/tex], som åpenbart er sant. Hvis vi kaller den likheten for Q så har du da i utgangspunktet vist at [tex]P \Rightarrow Q[/tex]. Men den implikasjonen som fullfører beviset er egentlig den motsatte implikasjonen [tex]Q \Rightarrow P[/tex]!

Det som gjør at beviset her likevel ikke er feil, er at det er ekvivalens mellom alle stegene fra P til Q. Det betyr at vi har [tex]P \Leftrightarrow Q[/tex], så vi har da også at [tex]Q \Rightarrow P[/tex]. Det er den implikasjonen som er viktig.

Når vi beviser ting må vi generelt aldri starte med å anta at det vi skal vise er sant. Å vise at det medfører at noe annet, som vi vet er sant, stemmer, beviser egentlig ingenting.

Jeg ville ført siste del av beviset slik:

[tex]S(k+1): 1+2+3+ ... + k + (k+1) = \frac{k(k+1)}{2} + k+1 = \frac{k(k+1)}{2} + \frac{2}{2}(k+1) = ... = \frac{(k+1)(k+2)}{2}[/tex],

altså ved å starte med summen og så gå steg for steg frem til det uttrykket vi skal vise at det blir.
Sist redigert av Vektormannen den 21/10-2012 17:01, redigert 1 gang totalt.
Elektronikk @ NTNU | nesizer
Aleks855
Rasch
Rasch
Innlegg: 6862
Registrert: 19/03-2011 15:19
Sted: Trondheim
Kontakt:

If I may... Jeg brukte vel også det samme eksempelet for induksjonsbevis i denne videoen. :)
Bilde
laustr
Cayley
Cayley
Innlegg: 54
Registrert: 06/01-2012 14:16

oja, haha. Har ikke sett noen av videoene. Ser nå at jeg skrev akkurat det som var sagt i videoen som "svinepels" postet XD. E visst en populær måte å forklare induksjonsbevis på det :P

Og takk for at du "rettet" induksjonsbeviset mitt, Vektormannen, som egentlig ikke hadde noen feil :P haha
dan
Dirichlet
Dirichlet
Innlegg: 188
Registrert: 25/09-2010 16:38

laustr skrev: I grunntrinnet skal du vise at det stemmer for et gitt tall, for eks. 1
I induksjonstrinnet skal du anta at det stemmer for et tall k (...)
Dette er ikke helt presist. Vi at det gjelder for alle tall fra den minste verdien åstanden er definert for, opp til en valgri grense. Dette utnytter vi når vi formulerer hypotesen; der antar vi at vi har sjekket at hypotesen holder for alle tall opp til en k. Men i prinsippet behøver vi kun å sjekke en enkelt verdi, ofte n= 0 eller n=1
rembrandt
Descartes
Descartes
Innlegg: 425
Registrert: 10/11-2011 08:47

Noen bruker k og noen bruker t, hvordan skal man avgjøre om hvilken tegn skal brukes under induksjonsprosess?

ser frem til svar.

Kan noen legge ut mer avansert eksempel som er typisk under eksamen?
When men, even unknowingly, are to meet one day, whatever may befall each, whatever the diverging paths, on the said day, they will inevitably come together in the red circle.
2357
Lagrange
Lagrange
Innlegg: 1180
Registrert: 07/12-2007 22:08

rembrandt skrev:Noen bruker k og noen bruker t, hvordan skal man avgjøre om hvilken tegn skal brukes under induksjonsprosess?
Det var da også noe å henge seg opp i. Det spiller ingen rolle hva du bruker, men hvis et symbol har en gitt betydning i oppgaven, er det lurt å velge et annet tegn i induksjonsantakelsen.
Svar