Andra steget i induktionsbevis

Vi börjar med att bevisa påståendet för något basfall, $n=a$ (för något värde på a). Därefter gör vi följande: Vi antar först att satsen gäller för ett godtyckligt värde. Därefter använder vi detta antagande för att bevisa att om påståendet är sant för $n=k$, då är påståendet också sant för $n=k+1$. 

Eftersom vi har bevisat att påståendet är sant för vårt basfall, $n=a$, måste det gälla att påståendet är sant för nästa värde på n, dvs. $n=a+1$. Och eftersom påståendet är sant för $n=a+1$, måste det också vara sant för $n=a+2$, och eftersom påståendet är sant för $n=a+2$, måste det också vara sant för $n=a+3$, och så vidare. 

Vi behöver därför basfallet, för att visa att vårt påstående som vi antar är sant, verkligen är sant (för åtminstone ett värde). 

Ofta beskrivs induktionsbevis som en rad med dominobrickor. Vi antar att en bricka faller – då kan vi bevisa att brickan framför också kommer att falla. Vårt basfall är då den första brickan som välter, och som får alla andra brickor att välta därefter. Att anta att ett felaktigt påstående stämmer, eller att vara utan basfall, och bygga vårt bevis på ett felaktigt påstående, är ungefär som att bevisa att "om bricka n välter, välter också bricka $n+1$, men utan att någonsin starta dominobrickorna. :)

Smutstvätt skrev:

Vi börjar med att bevisa påståendet för något basfall, $n=a$ (för något värde på a). Därefter gör vi följande: Vi antar först att satsen gäller för ett godtyckligt värde. Därefter använder vi detta antagande för att bevisa att om påståendet är sant för $n=k$, då är påståendet också sant för $n=k+1$. 

Eftersom vi har bevisat att påståendet är sant för vårt basfall, $n=a$, måste det gälla att påståendet är sant för nästa värde på n, dvs. $n=a+1$. Och eftersom påståendet är sant för $n=a+1$, måste det också vara sant för $n=a+2$, och eftersom påståendet är sant för $n=a+2$, måste det också vara sant för $n=a+3$, och så vidare. 

Vi behöver därför basfallet, för att visa att vårt påstående som vi antar är sant, verkligen är sant (för åtminstone ett värde). 

Ofta beskrivs induktionsbevis som en rad med dominobrickor. Vi antar att en bricka faller – då kan vi bevisa att brickan framför också kommer att falla. Vårt basfall är då den första brickan som välter, och som får alla andra brickor att välta därefter. Att anta att ett felaktigt påstående stämmer, eller att vara utan basfall, och bygga vårt bevis på ett felaktigt påstående, är ungefär som att bevisa att "om bricka n välter, välter också bricka n+1$$, men utan att någonsin starta dominobrickorna. :)

Det var inget - jag var dum.

Smutstvätt skrev:

Vi börjar med att bevisa påståendet för något basfall, $n=a$ (för något värde på a). Därefter gör vi följande: Vi antar först att satsen gäller för ett godtyckligt värde. Därefter använder vi detta antagande för att bevisa att om påståendet är sant för $n=k$, då är påståendet också sant för $n=k+1$. 

Eftersom vi har bevisat att påståendet är sant för vårt basfall, $n=a$, måste det gälla att påståendet är sant för nästa värde på n, dvs. $n=a+1$. Och eftersom påståendet är sant för $n=a+1$, måste det också vara sant för $n=a+2$, och eftersom påståendet är sant för $n=a+2$, måste det också vara sant för $n=a+3$, och så vidare. 

Vi behöver därför basfallet, för att visa att vårt påstående som vi antar är sant, verkligen är sant (för åtminstone ett värde). 

Ofta beskrivs induktionsbevis som en rad med dominobrickor. Vi antar att en bricka faller – då kan vi bevisa att brickan framför också kommer att falla. Vårt basfall är då den första brickan som välter, och som får alla andra brickor att välta därefter. Att anta att ett felaktigt påstående stämmer, eller att vara utan basfall, och bygga vårt bevis på ett felaktigt påstående, är ungefär som att bevisa att "om bricka n välter, välter också bricka n+1$$, men utan att någonsin starta dominobrickorna. :)

Ännu en fråga, förlåt om den är dum:

Jag fattar att vi använder basfallet och kan säga att om det gäller för n=k, då gäller det för k+1. Så om basfallet är n=a, då stämmer det även för a+1. Men det jag inte förstår är hur det implicierar att det även stämmer för a+2, a+3 osv.

Jag fattar att vi använder basfallet och kan säga att om det gäller för n=k, då gäller det för k+1. Så om basfallet är n=a, då stämmer det även för a+1. Men det jag inte förstår är hur det implicierar att det även stämmer för a+2, a+3 osv.

När vi bevisat att påståendet stämmer för $n=a+1$, då kan vi sätta detta värde som vårt nya "basfall". Eftersom påståendet gäller för fallet $n=a+1$ (vårt nya "basfall"), måste det också gälla för nästa värde på n, $n=(a+1)+1=a+2$. Därefter sätter vi $n=a+2$ som nytt "basfall", och då måste påståendet stämma även för nästa värde på n, $n=(a+2)+1=a+3$, och så vidare. :)

Ännu en fråga, förlåt om den är dum:

Inget sådant snack här! Syftet med att gå i skolan, och syftet med att komma hit till Pluggakuten, är att lära sig saker. Om du redan kunde allt skulle forumet inte behövas. En är inte dum bara för att en tagit sig an en ny sak och inte riktigt fått kläm på den ännu. ☺️

EDIT: Citationstecken tillagda för att förtydliga. 

Smutstvätt skrev:

Jag fattar att vi använder basfallet och kan säga att om det gäller för n=k, då gäller det för k+1. Så om basfallet är n=a, då stämmer det även för a+1. Men det jag inte förstår är hur det implicierar att det även stämmer för a+2, a+3 osv.

När vi bevisat att påståendet stämmer för $n=a+1$, då kan vi sätta detta värde som vårt nya basfall. Eftersom påståendet gäller för fallet $n=a+1$ (vårt nya basfall), måste det också gälla för nästa värde på n, $n=(a+1)+1=a+2$. Därefter sätter vi $n=a+2$ som nytt basfall, och då måste påståendet stämma även för nästa värde på n, $n=(a+2)+1=a+3$, och så vidare. :)

Ännu en fråga, förlåt om den är dum:

Inget sådant snack här! Syftet med att gå i skolan, och syftet med att komma hit till Pluggakuten, är att lära sig saker. Om du redan kunde allt skulle forumet inte behövas. En är inte dum bara för att en tagit sig an en ny sak och inte riktigt fått kläm på den ännu. ☺️

Men vi kan väl inte med säkerhet veta att det nya basfallet $n=a+1$ också kommer att gälla, eller? Beviset bygger ju på att vi säger att om det gäller för $n=k$, då kan vi säga att det också gäller för $k+1$.

Vi kan ju med säkerhet säga att det då gäller för basfallet $n=a\Rightarrow n=a+1$, men det är väl för att vi faktiskt testade basfallet, eller? Skulle man inte egentligen behöva testa varje nytt basfall, för att bekräfta att det fungerar, och sen säga att det då också gäller för talet därefter?

Vi antar att detta gäller oavsett värde på n. Det är därför vi väljer ett godtyckligt värde på n ($n=k$), snarare än ett givet värde (säg $n=7$). Då är antagandet giltigt oavsett värde på k. 

Tänk dig en lång rad med personer. Vi ger dessa personer en regel: om ni håller i den röda bollen, måste ni ge den till personen som står bredvid er. Därefter ger vi en person i ena änden en röd boll. Denna person måste nu ge bollen till personen som står bredvid. Då flyttar regeln vidare till den person som nu håller i bollen, och denna person måste nu ge bollen till nästa person som står bredvid hen. 

Smutstvätt skrev:

Vi antar att detta gäller oavsett värde på n. Det är därför vi väljer ett godtyckligt värde på n ($n=k$), snarare än ett givet värde (säg $n=7$). Då är antagandet giltigt oavsett värde på k. 

Tänk dig en lång rad med personer. Vi ger dessa personer en regel: om ni håller i den röda bollen, måste ni ge den till personen som står bredvid er. Därefter ger vi en person i ena änden en röd boll. Denna person måste nu ge bollen till personen som står bredvid. Då flyttar regeln vidare till den person som nu håller i bollen, och denna person måste nu ge bollen till nästa person som står bredvid hen. 

Men vi vet väl inte om det gäller för alla godtyckliga värden, det är väl bara ett antagande vi gör för att sedan säga att om det stämmer för ett godtyckligt värde $k$, gäller det också för $k+1$, eller missförstår jag någonting? Hur kan vi anta att det kommer gälla för alla värden på $k$?

Du vet ju att det gäller om n = 1 (basfallet, steg 1).  Om det är så att det stämmer när n = k+1 OM det stämde när n = k, så måste det ju stämma pm n = 2, och i så fall måste det stämma om n = 3. och i så fall ...

Smaragdalena skrev:

Du vet ju att det gäller om n = 1 (basfallet, steg 1).  Om det är så att det stämmer när n = k+1 OM det stämde när n = k, så måste det ju stämma pm n = 2, och i så fall måste det stämma om n = 3. och i så fall ...

Varför måste det det?

Du har ju visat att OM det stämmer för n = k, så stämmer det för n = k+1. Och du vet att det stämmer när n = k =  1, så då stämmer det när n = k+1 = 2, och då kan man välja att n = k = 2 och i så fall så stämmer det om n = k+1 = 3, och då kan man sätta n = k = 3 och ...

Smaragdalena skrev:

Du har ju visat att OM det stämmer för n = k, så stämmer det för n = k+1. Och du vet att det stämmer när n = k =  1, så då stämmer det när n = k+1 = 2, och då kan man välja att n = k = 2 och i så fall så stämmer det om n = k+1 = 3, och då kan man sätta n = k = 3 och ...

Ahh, jag tror äntligen jag förstår. Om det stämmer när n=1 stämmer det också när n=2, och om det stämmer när n=2 stämmer det också när n=3 osv. Tänker jag rätt?

Ja, det är så induktionsbevis fungerar.