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...
Matematisk induksjonsbevis- R2 pensum
Moderatorer: Aleks855, Gustav, Nebuchadnezzar, Janhaa, DennisChristensen, Emilga
Bachelor i matematiske fag NTNU - tredje år.
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
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
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...
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.
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.
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.
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å
må 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.
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å
må 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.
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
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.
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.
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
- 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.
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
If I may... Jeg brukte vel også det samme eksempelet for induksjonsbevis i denne videoen.
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 
Og takk for at du "rettet" induksjonsbeviset mitt, Vektormannen, som egentlig ikke hadde noen feil haha
Og takk for at du "rettet" induksjonsbeviset mitt, Vektormannen, som egentlig ikke hadde noen feil
hahaDette 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=1laustr 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 (...)
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?
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.
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.rembrandt skrev:Noen bruker k og noen bruker t, hvordan skal man avgjøre om hvilken tegn skal brukes under induksjonsprosess?