00:00
00:00
Så hjälper Eddler dig:
Videor som är lätta att förstå Övningar & prov med förklaringar
Allt du behöver för att klara av nationella provet
Så hjälper Eddler dig:
Videor som är lätta att förstå Övningar & prov med förklaringar
Allt du behöver för att klara av nationella provet

Vad är ett induktionsbevis?

Ett induktionsbevis kan liknas vid dominobrickor som faller. Du vill i denna typ av bevis göra det tydligt att om en bricka faller så kommer även nästa bricka att falla. Sedan skall detta medföra att alla brickor faller. Vanligt är att man har ett påstående som man vill visa stämmer.

Tex en likhet eller en olikhet som skall gälla. Man visar då att det stämmer för ett första fall och sedan att om det stämmer för ett generellt fall så skall också nästföljande fall stämma.

Om det stämmer för det första fallet och sedan det generella så har man visat att påståendet stämmer med hjälp av induktion.

Strategi för ett induktionsbevis

Den strategi som används när ett induktionsbevis genomförs är följande.

  1. Induktionsbas: Visa att påståendet gäller för n=an = a.
  2. Antagande: Antag att det gäller för n=pn = p.
    Induktionssteg: Visa att det då gäller då n=p+1n = p + 1.
  3. Slutsats: Eftersom det gäller för n=an = a (steg 1) och två på varandra följande fall (steg 2) så stämmer påståendet.

När du har genomfört och visat de tre stegen i strategin så kan induktionsbeviset sägas vara klart och du har då visat att ett påstående stämmer.

Exempel 1

Visa att  i=1n2k1\sum_{i=1}^n2^{k-1}i=1n2k1  kan skrivas som  1+2+4++2n11+2+4+…+2^{n-1}1+2+4++2n1 

Lösning

Vi ska med ett induktionsbevis visa att påstående gäller.

Induktionsbas, n = 1

 VL:211=20=1VL:2^{1-1}=2^0=1VL:211=20=1 

 HL:211=21=1HL:2^1-1=2-1=1HL:211=21=1 

VL=HLVL=HLVL=HL  och det stämmer för basfallet.

Induktionsantagande

 Vi antar att det stämmer för  n=pn=pn=p , dvs att  1+2+4++2p1=2p11+2+4+…+2^{p-1}=2^p-11+2+4++2p1=2p1 

Påstående

Vi vill nu visa att det stämmer för  n=p+1n=p+1n=p+1 , dvs att  1+2+3++p+p+1=1+2+3+…+p+p+1=1+2+3++p+p+1= (p+1)(p+1+1)2\frac{(p+1)(p+1+1)}{2}(p+1)(p+1+1)2   .

Med hjälp av antagandet kan vi skriva om VLVLVL enligt

VL=1+2+3++p+p+1=VL= 1+2+3+…+p+p+1 = p(p+1)2+p+1=p(p+1)2+2(p+1)2=\frac{p(p+1)}{2}+p+1=\frac{p(p+1)}{2}+\frac{2(p+1)}{2}=p(p+1)2 +p+1=p(p+1)2 +2(p+1)2 =  p(p+1)+2(p+1)2=(p+1)(p+2)2\frac{p(p+1)+2(p+1)}{2}=\frac{(p+1)(p+2)}{2}p(p+1)+2(p+1)2 =(p+1)(p+2)2  =HL= HL

Alltså gäller att VL=HLVL = HL.

Slutsats

Enligt principen för induktionsbevis ger induktionbas och induktionssteg att påståendet stämmer.

Exempel i videon

  1. Visa att k=1n2k=n(n+1) \sum_{k=1}^{n} 2k = n(n+1) för alla k ≥ 1.