Induktionsbevis: Nödvändigheten med första steget ?

Basfallet behöver inte vara n = 1 utan kan lika gärna vara n = 2 eller varför inte n = 28764, men man ska då komma ihåg att satsen som bevisas då endast gäller för n ≥ "basfallet".

Javisst, men hur pass nödvändigt är egentligen det (första) steget, då den informationen ändå lär visa sig då vi nyttjar k+1 ? Vad tillför n=1 som man inte kan erhålla då vi ansätter k+1 ?

Edit: Det beror väl lite på hur man lägger upp bevisföringen, men, jag menar om första steget i sig tillför något vitalt. Själv tycker jag det känns lite förlegat och pretentiöst gammalmodigt.

• Vi bevisar att det gäller för n=p
  
• Vi bevisar att, om det gäller för n = k (k > p) så gäller det även för n = k+1.
  
• Då är det väl uppenbart att man kan dra slutsatsen att det gäller för p, p + 1, p + 2, p + 3, ... ?

Du ansätter alltså inte att det gäller för n = k + 1. Du bevisar att givet att det gäller för n = k, så måste det gälla för n = k + 1.

Du vill ha ett exempel där basvillkoret behövs? Säg att satsen är att summan av alla naturliga tal mindre än eller lika med n är S(n) = 5 + n*(n+1)/2. Strunta nu i basvillkoret och antag att det gäller för n = k. Vi har då S(k) = 5 + k*(k+1)/2. Vad blir S(k+1)? Jo,

S(k+1) = S(k) + (k+1) = (av antagandet) = 5 + k*(k+1)/2 + (k+1) = 5 + (k*(k+1) + 2*(k+1))/2 = 5 + (k+1)*(k+2)/2.

Aha! Formeln gäller alltså även för n = k + 1. Vi har bevisat att S(n) = 5 + n*(n+1)/2.

Nej... för sätter vi in n = 1 fås

S(1) = 5+1*2/2 = 6

men vi vet ju att S(1) = 1.

Slusats: Vi behöver basvillkoret!

Menade använder.


Ja men då är man lite väl robotisk och trångsynt ? Det är väl bara göra samma resonemang med en formel som gäller för n=1, ej för n=2, men sedan för n=3,4,5... Att då blint förlita sig på n=1, "sedan godtyckligt n=k utan att tänka på n=2", ger ju oxo en felaktig bevisföring.

Jag förstår inte alls vad du menar.

Vi antar att det gäller för n = k och visar att det då gäller för n = k+1. Eftersom vi redan bevisat att det gäller för n = 1, vet vi då att det gäller för n = 2, och gäller det för n = 2 så gäller det för n = 3, osv. Alltså gäller det för alla naturliga tal.

Ok, bara hittar på en funktion och kör på som en robot. Visa att f(n)=(n-2)/(n-2)=1. n=1 => f(1)=1, antar f(n)=1 => f(n+1)= (n+1-2)/(n+1-2) = 1 om n\neq 2.

Detta innebär ju inte att f(2)=1 ändå.

Precis som du säger så gäller inte ditt bevis om n = 2 så vad är problemet?

Äsch, kanske glömmer det hela.. Det är bara en personlig åsikt att nyttjandet av ex. n=1 inte känns alls så meningsfullt och inte garanterar något förutom just i n=1.. och att man liksom måste "ha facit i hand" innan man väljer n=1 (eller om det är bättre med n=2 eller 3 eller ...)

EDIT: Sen är väl vissa saker mer eller mindre lämpade att bevisas genom induktion.

Nej, det är absolut inte en personlig åsikt. Såg du mitt exempel där vi struntade i det. Då kan det bli helt tokigt. På vilket sätt måste du ha "facit i hand"?

Ja det är ett bra exempel, med "rekursiv" bevisföring. Ser inte något omotiverande med n=1 då.

Fast, som jag försökte antyda med mitt exempel är att. Bara för att vi visar n=1, garanteras inte det att antagandet n=k är sann.

Nej givetvis inte, men det är ju ingen som säger. Du behöver båda ingredienserna för att baka kakan rätt.

En enkel analogi fås av vanlig satslogik.

A (antag A)
A -> B (av A följer B)
: B (alltså B)

Givetvis behöver du premissen (antagandet) att A gäller.

Eller för att ta analogin med dominobrickor. För att kunna dra slutsatsen att alla brickor faller, räcker det inte att veta att om en bricka faller så kommer nästa bricka att falla. Vi måste även veta att första brickan faller.

Petar ingen till den första brickan, får vi sitta i evighet och vänta på att brickorna skall falla.