Induktionsbevis

I avsnitten om talföljder och rekursion bekantade vi oss med olika typer av talföljder, och formler som vi kan använda oss av för att beräkna summan av värdena på elementen i en talföljd.

Att dessa formler för summan av värdena på elementen i en talföljd stämmer kan vi bevisa med hjälp av induktionsbevis. I det här avsnittet ska vi gå igenom hur ett induktionsbevis är uppbyggt och hur vi kan använda induktiv bevisföring för att bevisa talteoretiska satser.

Induktionsbevis

I Matte 4-kursen började vi lära oss hur bevisföring går till inom matematiken.

Nu ska vi gå igenom en typ av bevis som kallas induktionsbevis och som är väldigt användbart för att bevisa påståenden som har att göra med talföljder.

För att på ett informellt sätt förklara hur ett induktionsbevis allmänt fungerar, brukar man likna metoden med dominobrickor som är uppställda på en lång rad. Om brickorna är uppställda på rätt sätt och man puttar omkull den första dominobrickan, så kommer även den andra dominobrickan att falla, sedan den tredje, den fjärde, och så vidare, hur många brickor det än är som vi har ställt upp. Faller bricka p, så faller även nästa bricka (p+1).

När vi utför ett induktionsbevis behöver vi gå igenom tre viktiga steg för att kunna dra slutsatsen att det undersökta påståendet stämmer:

  1. Induktionsbasen. Visa att påståendet gäller för det första talet. (Detta kan jämföras med att den första dominobrickan faller.)
  2. Induktionsantagandet. Anta att påståendet gäller för något värde av n. (Detta kan jämföras med att vi antar att en viss dominobricka i raden av brickor faller.)
  3. Induktionssteget. Visa att om påståendet gäller för något värde av n, så gäller det även för nästa värde av n. (Detta kan jämföras med att visa att om den föregående dominobrickan föll, då kommer även nästa dominobricka att falla.)

Har vi lyckats gå igenom dessa tre steg, då har vi bevisat att det aktuella påståendet är sant även för alla tal som är större än det första talet. Om vi till exempel undersöker de positiva heltalen och lyckas visa att ett påstående gäller för induktionsbasen n = 1, antagit att påståendet gäller för något tal n = p och sedan visat att påståendet då även måste gälla för n = p + 1, då kan vi dra slutsatsen att eftersom påståendet gäller för n = 1, gäller det även för n = 2. Eftersom påståendet gäller för n = 2, gäller det även för n = 3, och så vidare, för alla tal n som är positiva heltal.

Summan av de n första positiva heltalen

Vi ska nu visa hur ett enkelt induktionsbevis kan se ut. Det påstående som vi ska bevis är att summan av de n första positiva heltalen

$$1+2+3+\,...\,+n$$

kan beräknas med uttrycket

$$\frac{n\cdot (n+1)}{2}$$

det vill säga att följande likhet gäller för alla heltal n ≥ 1:

$$1+2+3+\,...\,+n=\frac{n\cdot (n+1)}{2}$$

Vi börjar med att visa att påståendet stämmer för induktionsbasen, det vill säga då n = 1. Det gör vi genom att vi visar att det vänstra ledet (VL) i likheten ovan får samma värdet som det högra ledet (HL).

Då n = 1 får vi följande.

$$VL:\,\,1$$

$$HL:\,\,\frac{1\cdot (1+1)}{2}=\frac{2}{2}=1$$

Eftersom VL = HL vet vi nu att påståendet gäller för induktionsbasen n = 1. Därmed är vi klara med induktionsbevisets första del.

Den andra delen i vårt induktionsbevis består i att anta att påståendet gäller för något godtyckligt positivt heltal n = p, det vill säga att likheten VLp = HLp gäller.

Vårt antagande är alltså att följande likhet gäller:

$$1+2+3+\,...\,+p=\frac{p\cdot (p+1)}{2}$$

Den tredje delen i vårt bevis blir att visa att om påståendet stämmer för något positivt heltal n = p, då kommer påståendet även att stämma för nästa positiva heltal, det vill säga för n = p + 1. Detta är vad vi nu ska undersöka.

Det vänstra ledet (VLp+1) blir

$$1+2+3+\,...\,+p+(p+1)$$

det vill säga

$${VL}_{p+1}={VL}_{p}+(p+1)$$

Det högra ledet (HLp+1) blir

$$\frac{(p+1)\cdot ((p+1)+1)}{2}$$

Kan vi nu skriva om detta uttryck på formen

$${HL}_{p+1}={HL}_{p}+(p+1)$$

då har vi visat att likheten VLp+1 = HLp+1 gäller om VLp = HLp gäller.

Vi skriver därför om uttrycket i det högra ledet, HLp+1, på följande sätt:

$$\frac{(p+1)\cdot ((p+1)+1)}{2}=$$

$$=\frac{(p+1)\cdot (p+1)+(p+1)\cdot 1}{2}=$$

$$=\frac{p\cdot (p+1)+1\cdot (p+1)+(p+1)}{2}=$$

$$=\frac{p\cdot (p+1)+2\cdot (p+1)}{2}=$$

$$=\frac{p\cdot (p+1)}{2}+\frac{2\cdot (p+1)}{2}=$$

$$=\frac{p\cdot (p+1)}{2}+(p+1)$$

Nu har vi kommit fram till precis den form som vi ville kunna skriva detta uttryck på, så vi vet därför att följande likhet gäller:

$${HL}_{p+1}={HL}_{p}+(p+1)$$

Alltså är

$${VL}_{p+1}={HL}_{p+1}$$

om

$${VL}_{p}={HL}_{p}$$

Därmed är vi klara med det tredje steget i vårt induktionsbevis. Nu vet vi att det undersökta påståendet gäller för alla positiva heltal n ≥ 1.

Har du en fråga du vill ställa om Induktionsbevis? Ställ den på Pluggakuten.se
Har du hittat ett fel, eller har du kommentarer till materialet på den här sidan? Mejla matteboken@mattecentrum.se

Här går vi igenom induktionsbevis

  • Induktionsbevis: bevisteknik för att visa att påståenden stämmer, väldigt användbar för talföljder. Stegen i induktionsbevis är 1. Induktionsbasen 2. Induktionsantagandet 3. Induktionsteget.
  • Induktionsbasen: Vi visar att påståendet gäller för det första talet. 
  • Induktionsantagandet: vi antar att påståendet gäller för något värde av n. 
  • Induktionssteget: Vi visar att om påståendet gäller för något värde av n, så gäller det även för nästa värde av n.