Induktionsbevis

Teori

Exempel

Uppgifter

Läs mer

[redigera]

Ett induktionsbevis är en av de enklaste formerna för bevisföring inom matematiken. Det är den vanligaste bevismetoden när man arbetar med talföljder, alltså en följd av naturliga tal, där man vill bevisa att något gäller för exempelvis alla positiva tal. Grunden är väldigt enkel att förstå, och det går lätt att expandera till svårare problem om man förstår de steg man behöver ta.

Induktionsbevisets mall

1. Induktionsbas
   • Visa att det gäller för ett basfall. Hitta ett tal och använd detta för att visa ett exempel där ekvationen stämmer.
   • Den vanligaste basen för uppgifterna på denna nivå, är ett eller två.
   • Ibland kan man behöva två baser, beroende på hur ekvationen i uppgiften ser ut.
2. Induktionsantagande
   • Antag att ekvationen stämmer för en okänd variabel.
   • Ofta innehåller ekvationen n eller x, då byter man ut denna till p och skriver "Vi antar att ekvationen stämmer för n=p"
3. Induktionssteg
   • Här kommer själva beviset. Du sätter nu variabeln från förra steget till n=p+1. På detta sätt ska du visa att "om det stämmer för förra steget, så ska det fungera med detta steg. Därigenom har du visat att det gäller för alla tal.
   • Det svåra är att kunna koppla ihop induktionsantagandet med induktionssteget. Man vill kunna hitta ett mönster som är gemensamt mellan de två stegen, som ska skilja sig på ett sådant sätt att man ser hur de hänger ihop.
   • Se delen Exempel för en tydligare förklaring.
4. Avslutning
   • Här behöver man avsluta med en sammanfattning av vad man har bevisat, för vilka tal det är bevisat och att det gäller pga. induktionen.

[redigera]

Det första som behövs för är en sats eller ett påstående man vill bevisa. För detta exempel har vi följande påstående:
[math]\displaystyle{ 1+2+3+\cdots+n = \frac{n(n+1)}{2} }[/math]

Alltså, summan av alla positiva tal upp till talet n, kan skrivas som talet n gånger n+1, delat på talet 2. Vi vill nu se om detta stämmer för alla positiva tal från och med 1. Om vi bevisar detta i steg enligt mallen ovan, blir det som följer.

1. Induktionsbas
   • Vi visar först att satsen gäller för [math]\displaystyle{ n=1 }[/math].
   • Detta gör man genom att helt enkelt sätta in värdet 1 i ekvationen. Ofta kan det för enkelhetens skull vara bra att dela upp högerled (HL) och vänsterled (VL) var för sig, för att sedan jämföra dem.
   • [math]\displaystyle{ VL:1 }[/math]
   • [math]\displaystyle{ HL:\frac{1(1+1)}{2}=\frac{1(2)}{2}=\frac{2}{2}=1 }[/math]
   • Vi kan konstatera att [math]\displaystyle{ HL=VL }[/math]. Därmed har vi ett konstaterat basfall där antagandet stämmer.
2. Induktionsantagande
   • Vi antar att [math]\displaystyle{ 1+2+3+\cdots+n = \frac{n(n+1)}{2} }[/math] stämmer för fallet där [math]\displaystyle{ n=p }[/math].
   • Alltså att [math]\displaystyle{ 1+2+3+\cdots+p = \frac{p(p+1)}{2} }[/math]
3. Induktionssteg
   • Nu vill vi se om vi med hjälp av föregående steget kan visa att ekvationen stämmer när [math]\displaystyle{ n=p+1 }[/math]
   • [math]\displaystyle{ VL: 1+2+3+\cdots+p+(p+1) }[/math]
   • [math]\displaystyle{ HL: \frac{(p+1)((p+1)+1)}{2}=\frac{(p+1)(p+2)}{2} }[/math]
   • Vi kan se att vänsterledet är nästan samma sak som vänsterledet från antagandet, det skiljer sig bara på den sista termen. Eftersom vi antagit att ekvationen stämmer för [math]\displaystyle{ n=p }[/math] så kan vi använda antagandet i nuvarande steget.
   • [math]\displaystyle{ 1+2+3+\cdots+p+(p+1) = }[/math] (HL från antagandet)[math]\displaystyle{ +(p+1)= \frac{p(p+1)}{2}+(p+1)=\frac{p(p+1)}{2}+\frac{2(p+1)}{2}=\frac{(p(p+1))+(2(p+1))}{2}=\frac{(p^2+p)+(2p+2)}{2}=\frac{p^2+3p+2}{2}=\frac{(p+1)(p+2)}{2}= }[/math]HL från induktionssteget.
4. Avslutning
   • Vi har nu med hjälp av induktion visat att [math]\displaystyle{ 1+2+3+\cdots+n = \frac{n(n+1)}{2} }[/math] stämmer för alla positiva heltal tal från och med 1.

[redigera]

[redigera]